Routes With a Divisible Fare

A tram network is drawn as a grid fares. A rider starts at the top-left stop and ends at the bottom-right stop, moving only right or down; the fare of a ride is the sum of the numbers on every stop visited (both ends included). A promotion refunds rides whose fare is divisible by k. Return how many right/down routes have a fare divisible by k, modulo 10**9 + 7.

Examples

Input:  fares = [[1, 2, 3],
                 [4, 5, 6]], k = 3
Output: 1
Explanation: the three routes cost 12, 14 and 16; only 12 is divisible by 3.

Input:  fares = [[1, 2, 3],
                 [4, 5, 6]], k = 2
Output: 3

Constraints

• 1 <= rows, cols <= 60
• 0 <= fares[i][j] <= 100
• 1 <= k <= 50
• Target complexity: O(rows * cols * k).

Goals

• Add a remainder dimension to a grid DP
• Combine two different moduli without mixing them up