102286: [AtCoder]ABC228 G - Digits on Grid

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$.

问题描述

有一个网格，有$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}$。

求出$X$可以变成的不同整数的数量，对$998244353$取模。

约束

• $2 \leq H, W \leq 10$
• $1 \leq N \leq 300$
• $1 \leq c_{i, j} \leq 9$
• 输入中的所有值都是整数。

输入

输入通过标准输入给出以下格式：

$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}$

输出

打印出$X$可以变成的不同整数的数量，对$998244353$取模。

样例输入1

2 2 1
31
41

样例输出1

5

下面是可能的一种情况。

• 首先，Takahashi将棋子放在$(1, 2)$上。
• Takahashi将棋子从$(1, 2)$移动到$(1, 1)$，然后写下$(1, 1)$上的数字$3$。
• Aoki将棋子从$(1, 1)$移动到$(2, 1)$，然后写下$(2, 1)$上的数字$4$。

在这种情况下，我们有$X = 34$。
下面是另一种可能的情况。

• 首先，Takahashi将棋子放在$(2, 2)$上。
• Takahashi将棋子保留在$(2, 2)$上，然后写下$(2, 2)$上的数字$1$。
• Aoki将棋子从$(2, 2)$移动到$(1, 2)$，然后写下$(1, 2)$上的数字$1$。

在这种情况下，我们有$X = 11$。 除了这些之外，$X$还可以成为$33$、$44$或$43$，但不能成为其他数字。
也就是说，$X$可以变成的整数有五个，所以我们打印$5$。

样例输入2

2 3 4
777
777

样例输出2

1

$X$只能变成$77777777$。

样例输入3

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

样例输出3

685516949

确保对$998244353$取模。