G - Digits on Grid 解説 /

実行時間制限: 3 sec / メモリ制限: 1024 MB

配点 : 600 点

問題文

縦 H 行、横 W 列のマス目があり、それぞれのマスには 1 から 9 のいずれかの数字が書かれています。 1 \leq i \leq H かつ 1 \leq j \leq W を満たす整数の組 (i, j) それぞれについて、上から i 行目、 左から j 列目のマスに書かれた数字は c_{i, j} です。

高橋君と青木君はこのマス目を使って 2 人で遊びます。 まず、高橋君がいずれか 1 つのマスを選び、そのマスにコマを置きます。その後、2 人は下記の手順 1. から 4. を N 回繰り返します。

  1. 高橋君が次の 2 つのうちどちらか一方を行う。
    • 現在コマが置かれているマスと同じ行にある別のマスに、コマを移動する。
    • 何もしない。
  2. 高橋君が、現在コマが置かれているマスに書かれた数字を黒板に書く。
  3. 青木君が次の 2 つのうちどちらか一方を行う。
    • 現在コマが置かれているマスと同じ列にある別のマスに、コマを移動する。
    • 何もしない。
  4. 青木君が、現在コマが置かれているマスに書かれた数字を黒板に書く。

その後、黒板には 2N 個の数字が書かれています。それらの数字を黒板に書かれたのが早い順番に並べたものを d_1, d_2, \ldots, d_{2N} とします。 2 人は 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}\cdotsc_{1, W}
c_{2, 1}c_{2, 2}\cdotsc_{2, W}
\vdots
c_{H, 1}c_{H, 2}\cdotsc_{H, W}

出力

整数 X としてあり得るものが何通りあるかを、998244353 で割った余りを出力せよ。

入力例 1

2 2 1
31
41

出力例 1

5

例えば、以下の進行が考えられます。

  • まず高橋君がマス (1, 2) にコマを置く。
  • 高橋君がコマをマス (1, 2) からマス (1, 1) に動かす。その後、マス (1, 1) に書かれた数字 3 を黒板に書く。
  • 青木君がコマをマス (1, 1) からマス (2, 1) に動かす。その後、マス (2, 1) に書かれた数字 4 を黒板に書く。

この場合、X = 34 となります。
他の例として、以下の進行も考えられます。

  • まず高橋君がマス (2, 2) にコマを置く。
  • 高橋君がコマをマス (2, 2) から動かさず、マス (2, 2) に書かれた数字 1 を黒板に書く。
  • 青木君がコマをマス (2, 2) からマス (1, 2) に動かす。その後、マス (1, 2) に書かれた数字 1 を黒板に書く。

この場合、X = 11 となります。
X としてあり得る整数は、上記の例で示した 34, 11 の他にも 33, 44, 43 があります。また、それら以外の整数が X となることはありえません。
X としてあり得る整数の個数は 5 個であるので 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 で割った余りを出力することに注意して下さい。

Score : 600 points

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}\cdotsc_{1, W}
c_{2, 1}c_{2, 2}\cdotsc_{2, W}
\vdots
c_{H, 1}c_{H, 2}\cdotsc_{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.