题目描述

对于非负整数 $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$ 次以下操作：
  • 选择一个整数 $k$，满足 $0 \leq k \leq K-1$。
  • 然后，对 $A$ 按照 $10^k$ 位进行稳定排序。也就是说，对于 $d=0,1,\ldots,9$，定义 $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

输入

3 2 3
74 42 54
42 54 74

输出

5

样例 2

输入

2 1 1
2 3
3 2

输出

0

样例 3

输入

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$ 中出现的次数等于其在 $B$ 中出现的次数。

样例解释 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)$。

所有操作及其结果如下：

• $(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

不存在满足条件的操作方案。

样例解释 3

所有 $4^{100}$ 种操作方案都满足条件。

由 ChatGPT 4.1 翻译