问题描述

对于非负整数 $x$ 和 $k$，$x$ 的第 $k$ 个最低位是当 $\\bigl\\lfloor \\frac{x}{10^k}\\bigr\\rfloor$ 被 $10$ 除的余数。例如，$123$ 的第 $0$ 个、第 $1$ 个、第 $2$ 个和第 $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$。
  • 然后，按照第 $k$ 个最低位对 $A$ 进行稳定排序。也就是说，令 $A^{(d)}$ 是由 $A$ 中所有第 $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$ 在 $A$ 和 $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

设 $k_1$ 和 $k_2$ 分别是第一次和第二次迭代选择的 $k$。例如，如果 $k_1 = 0$ 且 $k_2 = 1$，则 $A$ 的变化如下。

• 按照第 $k_1$ 个（第 $0$ 个）最低位进行稳定排序，使得 $A = (42,74,54)$。
• 按照第 $k_2$ 个（第 $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}$ 种方式都满足条件。