ディスク #1 に長さ $m$ のバイナリ文字列 $s_1$ が保存されています。
その後、$n - 1$ 回の操作が行われます。$i$ 回目の操作では、ディスク $1 \le p_{i+1} \le i$ が選ばれ、そのディスク上の文字列 $s_{p_{i+1}}$ がディスク $i + 1$ にコピーされて $s_{i+1}$ が生成されます。ただし、コピーの過程で高々 $k$ 個のビットが反転する可能性があります(すなわち、高々 $k$ 箇所でエラーが発生します)。
最終的な $n$ 個のバイナリ文字列 $s_1, s_2, \dots, s_n$(それぞれの長さは $m$)がすべて与えられます。あなたの課題は、この最終状態をもたらす可能性のある列 $p_2, p_3, \dots, p_n$ が何通りあるかを求めることです。
答えは非常に大きくなる可能性があるため、$998244353$ で割った余りを求めてください。
入力
入力の $1$ 行目には、問題文で説明された $3$ つの整数 $n, m, k$($2 \le n \le 5000, 4 \le m \le 15000, 1 \le k \le 3$)が含まれます。$m$ は $4$ の倍数であることが保証されています。
続く $n$ 行のそれぞれには、長さ $m/4$ の $16$ 進文字列 $s'_i$ が含まれます。$s'_i$ の各文字は 0–9 または A–F のいずれかであり、ここで $\text{A} = 10, \text{B} = 11, \dots, \text{F} = 15$ です。
$16$ 進表現 $s'_i$ の各桁は、バイナリ文字列 $s_i$ の連続する $4$ ビットに対応します。具体的には、各桁 $s'_{i,j}$ に対して、$s'_{i,j} = 8a + 4b + 2c + d$ かつ $a, b, c, d \in \{0, 1\}$ を満たす組 $(a, b, c, d)$ が一意に存在することが証明できます。バイナリ文字列 $s_i$ のビットは $(s_{i,4j}, s_{i,4j+1}, s_{i,4j+2}, s_{i,4j+3}) = (a, b, c, d)$ を満たします。
出力
有効な列 $(p_2, p_3, \dots, p_n)$ の個数を $998244353$ で割った余りを表す整数を $1$ つ出力してください。
入出力例
5 8 2
95
05
BD
9C
BD
6