Score : $600$ points

问题描述

存在一个由 $H$ 行和 $W$ 列构成的网格，其中每个格子包含一个介于 $1$ 和 $9$ 之间的数字。对于每一对整数 $(i, j)$ 满足 $1 \leq i \leq H$ 且 $1 \leq j \leq W$，在第 $i$ 行从上到下、第 $j$ 列从左到右的格子上的数字为 $c_{i, j}$。

使用这个网格，Takahashi 和 Aoki 将一起进行游戏。首先，Takahashi 选择一个格子并在其上放置一枚棋子。然后，两人将重复以下步骤 1 至 4，共进行 $N$ 次。

1. Takahashi 执行以下两种操作之一。
   • 将棋子移动到与当前棋子所在格子同一行的另一个格子上。
   • 保持不动。
2. Takahashi 在黑板上写下棋子所在格子上的数字。
3. Aoki 执行以下两种操作之一。
   • 将棋子移动到与当前棋子所在格子同一列的另一个格子上。
   • 保持不动。
4. Aoki 在黑板上写下棋子所在格子上的数字。

之后，黑板上将会有 $2N$ 个数字。设这些数字按照书写顺序分别为 $d_1, d_2, \ldots, d_{2N}$。两个男孩将以这种顺序连接这 $2N$ 位数字，组成一个 $2N$ 位整数 $X := d_1d_2\ldots d_{2N}$。

找出模 $998244353$ 后，$X$ 可以成为的不同整数的数量。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

There is a grid with $H$ horizontal rows and $W$ vertical columns, where each square contains a digit between $1$ and $9$. For each pair of integers $(i, j)$ such that $1 \leq i \leq H$ and $1 \leq j \leq W$, the digit written on the square at the $i$-th row from the top and $j$-th column from the left is $c_{i, j}$.

Using this grid, Takahashi and Aoki will play together. First, Takahashi chooses a square and puts a piece on it. Then, the two will repeat the following procedures, 1. through 4., $N$ times.

1. Takahashi does one of the following two actions.
   • Move the piece to another square that shares a row with the square the piece is on.
   • Do nothing.
2. Takahashi writes on a blackboard the digit written on the square the piece is on.
3. Aoki does one of the following two actions.
   • Move the piece to another square that shares a column with the square the piece is on.
   • Do nothing.
4. Aoki writes on the blackboard the digit written on the square the piece is on.

After that, there will be $2N$ digits written on the blackboard. Let $d_1, d_2, \ldots, d_{2N}$ be those digits, in the order they are written. The two boys will concatenate the $2N$ digits in this order to make a $2N$-digit integer $X := d_1d_2\ldots d_{2N}$.

Find the number, modulo $998244353$, of different integers that $X$ can become.

Constraints

• $2 \leq H, W \leq 10$
• $1 \leq N \leq 300$
• $1 \leq c_{i, j} \leq 9$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$H$ $W$ $N$

$c_{1, 1}$$c_{1, 2}$$\cdots$$c_{1, W}$

$c_{2, 1}$$c_{2, 2}$$\cdots$$c_{2, W}$

$\vdots$

$c_{H, 1}$$c_{H, 2}$$\cdots$$c_{H, W}$

Output

Print the number, modulo $998244353$, of different integers that $X$ can become.

Sample Input 1

2 2 1
31
41

Sample Output 1

5

Below is one possible scenario.

• First, Takahashi puts the piece on $(1, 2)$.
• Takahashi moves the piece from $(1, 2)$ to $(1, 1)$, and then writes the digit $3$ written on $(1, 1)$.
• Aoki moves the piece from $(1, 1)$ to $(2, 1)$, and then writes the digit $4$ written on $(2, 1)$.

In this case, we have $X = 34$.
Below is another possible scenario.

• First, Takahashi puts the piece on $(2, 2)$.
• Takahashi keeps the piece on $(2, 2)$, and then writes the digit $1$ written on $(2, 2)$.
• Aoki moves the piece from $(2, 2)$ to $(1, 2)$, and then writes the digit $1$ written on $(1, 2)$.

In this case, we have $X = 11$. Other than these, $X$ can also become $33$, $44$, or $43$, but nothing else.
That is, there are five integers that $X$ can become, so we print $5$.

Sample Input 2

2 3 4
777
777

Sample Output 2

1

$X$ can only become $77777777$.

Sample Input 3

10 10 300
3181534389
4347471911
4997373645
5984584273
1917179465
3644463294
1234548423
6826453721
5892467783
1211598363

Sample Output 3

685516949

Be sure to find the count modulo $998244353$.

update @ 2024/3/10 10:00:18