/ 
Time Limit: 4 sec / Memory Limit: 1024 MB
配点 : 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 を置き換える．
このような手順は 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} 通りの手順すべてが条件を満たします．
Score : 900 points
Problem Statement
For non-negative integers x and k, the k-th lowest digit of x is the remainder when \bigl\lfloor \frac{x}{10^k}\bigr\rfloor is divided by 10. For instance, the 0-th, 1-st, 2-nd, and 3-rd lowest digits of 123 are 3, 2, 1, and 0, respectively.
You are given positive integers N, M, K, and sequences of non-negative integers A = (A_1, \ldots, A_N) and B = (B_1, \ldots, B_N).
Consider rearranging A by the following process.
- Do the following M times.
- Choose an integer k such that 0\leq k \leq K - 1.
- Then, perform a stable sort on A by k-th lowest digit. That is, let A^{(d)} be the subsequence of A composed of all elements of A whose k-th lowest digits are d, and replace A with the concatenation of A^{(0)}, A^{(1)}, \ldots, A^{(9)} in this order.
There are K^M ways to execute this process. How many of them end up making A equal B? Find this count modulo 998244353.
Constraints
- 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 and B are equal as multisets. That is, every integer x occurs the same number of times in A and B.
Input
The input is given from Standard Input in the following format:
N M K A_1 \ldots A_N B_1 \ldots B_N
Output
Print the number, modulo 998244353, of ways to execute the process that end up making A equal B.
Sample Input 1
3 2 3 74 42 54 42 54 74
Sample Output 1
5
Let k_1 and k_2 be the k chosen in the first and second iterations, respectively. For instance, if k_1 = 0 and k_2 = 1, then A changes as follows.
- A stable sort by k_1-th (0-th) lowest digit makes A = (42,74,54).
- A stable sort by k_2-th (1-st) lowest digit makes A = (42,54,74).
Here are all the ways to execute the process and the resulting 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 Input 2
2 1 1 2 3 3 2
Sample Output 2
0
There is no way to satisfy the condition.
Sample Input 3
5 100 4 0 12 34 56 78 0 12 34 56 78
Sample Output 3
982924732
All 4^{100} ways satisfy the condition.