配点 : $900$ 点

問題文

非負整数 $x, k$ に対して，$x$ の $10^k$ の位とは，$\bigl\lfloor \frac{x}{10^k}\bigr\rfloor$ を $10$ で割った余りのことをいいます．例えば $123$ の $10^0$, $10^1$, $10^2$, $10^3$ の位はそれぞれ $3, 2, 1, 0$ です．

正整数 $N, M, K$ および非負整数列 $A = (A_1, \ldots, A_N)$, $B = (B_1, \ldots, B_N)$ が与えられます．

次の手順によって $A$ を並べ替えることを考えます．

• 次を $M$ 回行う：- $0\leq k \leq K - 1$ となる整数 $k$ をひとつ選ぶ．
  • その後，$A$ を $10^k$ の位に関して安定ソートする．つまり，$d=0,1,\ldots,9$ に対して，$A$ の部分列 $A^{(d)}$ を $A$ の要素のうち $10^k$ の位が $d$ であるようなもの全体として定め，$A^{(0)}, A^{(1)}, \ldots, A^{(9)}$ をこの順に連結してできる列で $A$ を置き換える．
• $0\leq k \leq K - 1$ となる整数 $k$ をひとつ選ぶ．
• その後，$A$ を $10^k$ の位に関して安定ソートする．つまり，$d=0,1,\ldots,9$ に対して，$A$ の部分列 $A^{(d)}$ を $A$ の要素のうち $10^k$ の位が $d$ であるようなもの全体として定め，$A^{(0)}, A^{(1)}, \ldots, A^{(9)}$ をこの順に連結してできる列で $A$ を置き換える．

このような手順は $K^M$ 通りありますが，その結果 $A$ が $B$ に等しくなるものの個数を $998244353$ で割った余りを求めてください．

制約

• $1\leq N\leq 2\times 10^5$
• $1\leq M\leq 10^9$
• $1\leq K\leq 18$
• $0\leq A_i < 10^K$
• $0\leq B_i < 10^K$
• $A$ と $B$ は多重集合として一致する．つまり任意の整数 $x$ に対して，$x$ が $A$ に現れる回数は $x$ が $B$ に現れる回数と一致する．

入力

入力は以下の形式で標準入力から与えられます．

$N$ $M$ $K$

$A_1$ $\ldots$ $A_N$

$B_1$ $\ldots$ $B_N$

出力

$A$ が $B$ に等しくなるような手順の個数を $998244353$ で割った余りを出力してください．

3 2 3
74 42 54
42 54 74

5

$1$ 回目に選ぶ $k$ を $k_1$，$2$ 回目に選ぶ $k$ を $k_2$ とします．例えば $k_1 = 0, k_2 = 1$ のとき $A$ は次のように変化します．

• $10^{k_1} = 10^0$ の位に関する安定ソートにより，$A$ は $(42,74,54)$ になる．
• $10^{k_2} = 10^1$ の位に関する安定ソートにより，$A$ は $(42,54,74)$ になる．

すべての手順および，その結果の $A$ は以下の通りです：

• $(k_1, k_2) = (0,0)$：$A = (42,74,54)$．
• $(k_1, k_2) = (0,1)$：$A = (42,54,74)$．
• $(k_1, k_2) = (0,2)$：$A = (42,74,54)$．
• $(k_1, k_2) = (1,0)$：$A = (42,54,74)$．
• $(k_1, k_2) = (1,1)$：$A = (42,54,74)$．
• $(k_1, k_2) = (1,2)$：$A = (42,54,74)$．
• $(k_1, k_2) = (2,0)$：$A = (42,74,54)$．
• $(k_1, k_2) = (2,1)$：$A = (42,54,74)$．
• $(k_1, k_2) = (2,2)$：$A = (74,42,54)$．

2 1 1
2 3
3 2

0

条件を満たす手順は存在しません．

5 100 4
0 12 34 56 78
0 12 34 56 78

982924732

$4^{100}$ 通りの手順すべてが条件を満たします．