{"raw_statement":[{"iden":"problem statement","content":"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.\nYou 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)$.\nConsider rearranging $A$ by the following process.\n\n*   Do the following $M$ times.\n    *   Choose an integer $k$ such that $0\\leq k \\leq K - 1$.\n    *   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.\n\nThere are $K^M$ ways to execute this process. How many of them end up making $A$ equal $B$? Find this count modulo $998244353$."},{"iden":"constraints","content":"*   $1\\leq N\\leq 2\\times 10^5$\n*   $1\\leq M\\leq 10^9$\n*   $1\\leq K\\leq 18$\n*   $0\\leq A_i < 10^K$\n*   $0\\leq B_i < 10^K$\n*   $A$ and $B$ are equal as multisets. That is, every integer $x$ occurs the same number of times in $A$ and $B$."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$ $M$ $K$\n$A_1$ $\\ldots$ $A_N$\n$B_1$ $\\ldots$ $B_N$"},{"iden":"sample input 1","content":"3 2 3\n74 42 54\n42 54 74"},{"iden":"sample output 1","content":"5\n\nLet $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.\n\n*   A stable sort by $k_1$\\-th ($0$\\-th) lowest digit makes $A = (42,74,54)$.\n*   A stable sort by $k_2$\\-th ($1$\\-st) lowest digit makes $A = (42,54,74)$.\n\nHere are all the ways to execute the process and the resulting $A$.\n\n*   $(k_1, k_2) = (0,0)$: $A = (42,74,54)$.\n*   $(k_1, k_2) = (0,1)$: $A = (42,54,74)$.\n*   $(k_1, k_2) = (0,2)$: $A = (42,74,54)$.\n*   $(k_1, k_2) = (1,0)$: $A = (42,54,74)$.\n*   $(k_1, k_2) = (1,1)$: $A = (42,54,74)$.\n*   $(k_1, k_2) = (1,2)$: $A = (42,54,74)$.\n*   $(k_1, k_2) = (2,0)$: $A = (42,74,54)$.\n*   $(k_1, k_2) = (2,1)$: $A = (42,54,74)$.\n*   $(k_1, k_2) = (2,2)$: $A = (74,42,54)$."},{"iden":"sample input 2","content":"2 1 1\n2 3\n3 2"},{"iden":"sample output 2","content":"0\n\nThere is no way to satisfy the condition."},{"iden":"sample input 3","content":"5 100 4\n0 12 34 56 78\n0 12 34 56 78"},{"iden":"sample output 3","content":"982924732\n\nAll $4^{100}$ ways satisfy the condition."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}