問題文

非負整数 $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$ を置き換える．

このような手順は $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$ で割った余りを出力してください．

入力例 1

3 2 3
74 42 54
42 54 74

出力例 1

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

2 1 1
2 3
3 2

出力例 2

0

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

入力例 3

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

出力例 3

982924732

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