Equal Bottle Absorption Path Counting

In an instant, a huge \( n \times m \) matrix appears on the ground. Each cell contains a certain amount of magic liquid, an integer in the range \(0\) to \(k\). Two friends, Xiao A and Uim, are given a magic bottle each. They are allowed to choose any cell as the starting point and then travel along a path moving only right or down, ending at any cell. The absorption procedure is as follows:

• At the starting cell Xiao A absorbs the liquid,
• Then they alternate: the next cell is absorbed by Uim, then by Xiao A, and so on.

The path must contain an even number of cells so that the last absorption is always performed by Uim. Each magic bottle has capacity \(k\). The bottles work in a cyclic fashion: if a bottle, after absorbing, would contain \(k+1\) units, it is instead emptied to \(0\); if it would contain \(k+2\) units, it will hold \(1\); and generally, if the absorbed total is \(x\), then the bottle will finally contain \(x \bmod (k+1) \) units.

The final condition is that both bottles should hold the same amount of magic liquid, i.e. if we denote

[ S_A \equiv \text{(sum of elements absorbed by Xiao A)} \bmod (k+1), \quad S_U \equiv \text{(sum absorbed by Uim)} \bmod (k+1), ]

we require \(S_A \equiv S_U \pmod{(k+1)}\). Two different ways are considered distinct if they have a different starting cell or path. Your task is to count the number of valid paths modulo \(998244353\).

Note: A path is valid only if it contains at least 2 cells (so that the final absorption is done by Uim).

inputFormat

The first line contains three integers \(n\), \(m\), and \(k\) \((1 \le n, m \le \text{small constraints},\ 0 \le k \le \text{small integer})\).

Then follow \(n\) lines, each containing \(m\) integers. The \(j\)-th integer in the \(i\)-th line represents the amount of magic liquid in cell \((i, j)\), which is between \(0\) and \(k\) (inclusive).

outputFormat

Output a single integer, the number of valid paths modulo \(998244353\).

sample

2 2 1
0 1
1 0

0