AT_arc158_f [ARC158F] Random Radix Sort

[problemUrl]: https://atcoder.jp/contests/arc158/tasks/arc158_f 非負整数 $ 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 $ で割った余りを出力してください．

### 制約 - $ 1\leq\ N\leq\ 2\times\ 10^5 $ - $ 1\leq\ M\leq\ 10^9 $ - $ 1\leq\ K\leq\ 18 $ - $ 0\leq\ A_i\