AT_arc158_f [ARC158F] Random Radix Sort

对于非负整数 $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 \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 翻译