题目描述

非負整数 $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$ で割った余りを求めてください．

输入格式

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

$N$ $M$ $K$ $A_1$ $\ldots$ $A_N$ $B_1$ $\ldots$ $B_N$

输出格式

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

题目大意

给出正整数 $N,M,K$ 和非负整数序列 $A=(A_1​\dots,A_N​),B=(B_1​,\dots,B_N​)$ 。

对 $A$ 进行 $K^M$ 次排序，每次可选 $10$ 进制下从低到高第 $0\le k<K$ 位为关键字进行稳定升序排序。

求结果 $A$ 等于 $B$ 的方案数，对 $998244353$ 取模。

3 2 3
74 42 54
42 54 74

5

2 1 1
2 3
3 2

0

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

982924732

提示

制約

• $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$ に現れる回数と一致する．

Sample Explanation 1

$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)$．

Sample Explanation 2

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

Sample Explanation 3

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