P1373 The Great Escape of Xiao a and uim

Xiao a and uim came to explore the rainforest. Suddenly a north wind blew, a dark cloud surged in from the northern horizon with flashes of lightning and peals of thunder. In an instant, a gale rose, dark clouds covered the sky, and then big raindrops fell from above. A disheveled, green-faced, tusked monster appeared ahead, and said in a deep voice: "Hehe, since you have come here, only one of you can survive!" Xiao a and his partner were stunned.

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.

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 a single integer: the number of ways. Since the answer may be large, output it modulo $1,000,000,007$.

[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