Rikka with Seam

Seam carving is a novel algorithm for resizing images while maintaining as much information as possible from the source image.

Now, Rikka is going to use seam carving method to deal with an $n \times m$ black and white picture. We can abstract this picture into an $n \times m$ 01 matrix $A$.

A $K$-seam of this picture is an integer sequence $a$ which satisfies the following conditions:
1. $|a| = n$, $a_i \in [1, m]$.
2. $|a_i - a_{i+1}| \leq K$, $\forall i \in [1,n)$.

After choosing a $K$-seam $a$, Rikka reduces the size of the picture by deleting pixels $(i,a_i)$, and then she gets a matrix $A'$ of size $n \times (m - 1)$.

For example, if the chosen seam is $[1,2,3]$ and the picture is \begin{align*} \begin{bmatrix} 1 &0 &0 \\ 1& 1& 1 \\ 0 & 0& 0\end{bmatrix}\end{align*} the result matrix will be \begin{align*} \begin{bmatrix} 0 &0 \\ 1& 1 \\ 0 & 0\end{bmatrix}\end{align*}

Rikka finds that deleting different seams may get the same result. In the previous example, seam $[1,2,3],[1,2,1],[1,2,2],[1,1,1]$ are equivalent.

Now Rikka wants to calculate the number of different matrixes she can get by deleting exactly one $K$-seam.

The first line contains a single integer $t(1 \leq t \leq 10^3)$, the numebr of testcases.

For each testcase, the first line contains three numbers $n,m,K(2 \leq n,m \leq 2 \times 10^3, 1\leq K \leq m)$.

Then $n$ lines follow, each line contains a 01 string of length $m$ which describes one row of the matrix.

The input guarantees that there are at most $5$ testcases with $\max (n,m) > 300$.

For each testcase, output a single line with a single number, the answer modulo $998244353$.

3
2 2 1
00
10
5 5 1
00100
10101
00100
01000
11101
5 5 2
00100
10101
00100
01000
11101

2
70
199

2018 Multi-University Training Contest 9