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.

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.

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.

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.

见题面 Input 部分

见题面 Output 部分