{"problem":{"name":"Dice","description":{"content":"There are two dice, called die $1$ and die $2$. *   Die $1$ is an $N$\\-sided die, where each side shows a distinct positive integer $A_1, A_2, \\dots, A_N$ with equal probability. *   Die $2$ is an $M","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":4000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"fps_24_q"},"statements":[{"statement_type":"Markdown","content":"There are two dice, called die $1$ and die $2$.\n\n*   Die $1$ is an $N$\\-sided die, where each side shows a distinct positive integer $A_1, A_2, \\dots, A_N$ with equal probability.\n*   Die $2$ is an $M$\\-sided die, where each side shows a distinct positive integer $B_1, B_2, \\dots, B_M$ with equal probability.\n\nYou are also given a positive integer $K$.  \nFor each $k = 1, 2, \\dots, K$, solve the following problem:\n\n*   When rolling die $1$ and die $2$ simultaneously, compute the expected value of $(\\text{sum of the outcomes})^k$ modulo $998244353$.\n\nWhat does expected value modulo $998244353$ mean? It can be proven that the expected value is always a rational number. Under the constraints of this problem, if the value can be expressed as $\\tfrac{P}{Q}$ with coprime integers $P$ and $Q$, then there exists a unique integer $R$ such that $R \\times Q \\equiv P \\pmod{998244353}$ and $0 \\leq R < 998244353$. You are asked to compute this $R$.\n\n## Constraints\n\n*   $1 \\leq N \\leq 10^5$\n*   $1 \\leq M \\leq 10^5$\n*   $1 \\leq K \\leq 10^5$\n*   $1 \\leq A_1 < A_2 < \\dots < A_N \\leq 10^8$\n*   $1 \\leq B_1 < B_2 < \\dots < B_M \\leq 10^8$\n*   All input values are integers\n\n## Input\n\nThe input is given from standard input in the following format:\n\n$N$ $M$ $K$\n$A_1$ $A_2$ $\\dots$ $A_N$\n$B_1$ $B_2$ $\\dots$ $B_M$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"fps_24_q","tags":[],"sample_group":[["3 2 3\n1 2 3\n4 5","499122183\n166374102\n499122469\n\nFor example, if die $1$ shows $3$ and die $2$ shows $5$, then the cube of the sum is $(3+5)^3 = 512$."],["8 9 5\n26056440 37770730 49119845 54471601 59187620 86450214 95205990 97771081\n12521133 14054302 19786177 21524935 39265456 53591023 65158870 86176948 87221915","981084750\n45312313\n562611236\n522662310\n196292405"]],"created_at":"2026-03-03 11:01:14"}}