题目描述

给你一个下标从 0  开始的 $m \times n$ 整数矩阵 $grid$ 和一个整数 $k$ 。你从起点 $(0, 0)$ 出发，每一步只能往 下  或者往 右  ，你想要到达终点 $(m - 1, n - 1)$ 。

请你返回路径和能被 $k$ 整除的路径数目，由于答案可能很大，返回答案对 $10^9 + 7$  取余  的结果。

输入格式

第一行三个空格分隔的整数 $m,n,k$；

接下来 $m$ 行，每行 $n$ 个空格分隔的整数表示 $grid[i]$ 中的元素。

输出格式

一行一个整数表示答案。

示例 1：

3 3 3
5 2 4
3 0 5
0 7 2

2

解释: 有两条路径满足路径上元素的和能被 k 整除。

第一条路径为上图中用红色标注的路径，和为 5 + 2 + 4 + 5 + 2 = 18 ，能被 3 整除。

第二条路径为上图中用蓝色标注的路径，和为 5 + 3 + 0 + 5 + 2 = 15 ，能被 3 整除。

示例 2：

1 2 5
0 0

1

解释: 红色标注的路径和为 0 + 0 = 0 ，能被 5 整除。

示例 3：

3 4 1
7 3 4 9
2 3 6 2
2 3 7 0

10

解释: 每个数字都能被 1 整除，所以每一条路径的和都能被 k 整除。

提示：

• $m == grid.length$
• $n == grid[i].length$
• $1 <= m, n <= 5 * 10^4$
• $1 <= m * n <= 5 * 10^4$
• $0 <= grid[i][j] <= 100$
• $1 <= k <= 50$

SOURCE

矩阵中和能被 K 整除的路径