Description

In a flash, a gigantic $n \times m$ matrix appeared on the ground, and each cell of the matrix held an amount of magic fluid between $0 \sim k$.

The monster gave Xiao a and uim a magic bottle each, and said: You may start from any cell of the matrix, move one step to the right or down each time, and end at any cell. At the start, Xiao a uses his bottle to absorb the magic fluid on the ground; on the next step, uim absorbs; and so on, alternating. Moreover, the last absorption must be performed by uim. Each magic bottle has capacity $k$, meaning the amount in a bottle is always taken modulo $k+1$: if it reaches $k+1$ it resets to $0$, if it reaches $k+2$ it becomes $1$, and so on.

The monster also said that whoever has more magic fluid in their bottle at the end will survive. Xiao a and uim are very close, like brothers. How could he bear to let his partner perish? After a brief silence, Xiao a had a brainwave: if the amounts in their bottles are the same, both can survive. Xiao a and his partner burst into laughter.

Now he wants to know in how many ways both of them can survive.

Input Format

The first line contains three integers $n, m, k$ separated by spaces.

The next $n$ lines each contain $m$ integers, representing the amount of magic fluid in each cell of the matrix. Numbers in the same row are separated by spaces.

Output Format

Output a single integer: the number of ways. Since the answer may be large, output it modulo $1,000,000,007$.

2 2 3
1 1
1 1

4

Hint

[Problem Source]

Adapted by lzn.

[Sample Explanation]

Sample explanation: The four valid schemes are: $(1,1)\to (1,2)$, $(1,1)\to (2,1)$, $(1,2)\to (2,2)$, $(2,1)\to (2,2)$.

[Constraints]

For $20\%$ of the testdata, $n, m \leq 10$, $k \leq 2$. For $50\%$ of the testdata, $n, m \leq 100$, $k \leq 5$. For $100\%$ of the testdata, $1 \leq n, m \leq 800$, $1 \leq k \leq 15$.

Translated by ChatGPT 5