题目描述

给定一个 $r\times c$ 的整数网格 $a_{i,j}$。Aki 从 $(1,1)$ 出发，只能向右或向下走，直到到达 $(r,c)$。一条路径的权值为经过的格子数值之和。

请你统计：有多少条路径满足路径权值对 $k$ 取模为 0。答案对 $10^9+7$ 取模。

输入格式

第一行三个整数 $r,c,k$。 接下来 $r$ 行，每行 $c$ 个整数，表示 $a_{i,j}$。

• $1\le r,c\le 50$
• $1\le k\le 50$
• $0\le a_{i,j}\le 10^9$

输出格式

输出满足条件的路径条数（对 $10^9+7$ 取模）。

2 3 3
1 2 3
4 5 6

1