{"raw_statement":[{"iden":"problem statement","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$."},{"iden":"constraints","content":"*   $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"},{"iden":"input","content":"The 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$"},{"iden":"sample input 1","content":"3 2 3\n1 2 3\n4 5"},{"iden":"sample output 1","content":"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$."},{"iden":"sample input 2","content":"8 9 5\n26056440 37770730 49119845 54471601 59187620 86450214 95205990 97771081\n12521133 14054302 19786177 21524935 39265456 53591023 65158870 86176948 87221915"},{"iden":"sample output 2","content":"981084750\n45312313\n562611236\n522662310\n196292405"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}