6186: ABC228 —— G - Digits on Grid
[Creator : ]
Description
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.
Find the number, modulo $998244353$, of different integers that $X$ can become.
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.
-
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.
- Takahashi writes on a blackboard the digit written on the square the piece is on.
-
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.
- Aoki writes on the blackboard the digit written on the square the piece is on.
Find the number, modulo $998244353$, of different integers that $X$ can become.
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}$
$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.
Constraints
$2≤H,W≤10\\
1 \leq N \leq 300\\
1 \leq c_{i, j} \leq 9$
All values in input are integers.
1 \leq N \leq 300\\
1 \leq c_{i, j} \leq 9$
All values in input are integers.
Sample 1 Input
2 2 1
31
41
Sample 1 Output
5
Below is one possible scenario.
Below is another possible scenario.
That is, there are five integers that $X$ can become, so we print $5$.
- 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).
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).
That is, there are five integers that $X$ can become, so we print $5$.
Sample 2 Input
2 3 4
777
777
Sample 2 Output
1
X can only become $77777777$.
Sample 3 Input
10 10 300
3181534389
4347471911
4997373645
5984584273
1917179465
3644463294
1234548423
6826453721
5892467783
1211598363
Sample 3 Output
685516949