AT_abc228_g [ABC228G] Digits on Grid

[problemUrl]: https://atcoder.jp/contests/abc228/tasks/abc228_g 縦 $ 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 $ で割った余りを出力してください。

N/A

N/A

### 制約 - $ 2\ \leq\ H,\ W\ \leq\ 10 $ - $ 1\ \leq\ N\ \leq\ 300 $ - $ 1\ \leq\ c_{i,\ j}\ \leq\ 9 $ - 入力はすべて整数 ### Sample Explanation 1 例えば、以下の進行が考えられます。 - まず高橋君がマス $ (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 $ を出力します。 ### Sample Explanation 2 整数 $ X $ としてあり得るのは、$ 77777777 $ のみです。 ### Sample Explanation 3 $ 998244353 $ で割った余りを出力することに注意して下さい。