{"raw_statement":[{"iden":"problem statement","content":"Let $L=10^8$.\nYou are given an integer $N$ and a non-negative integer sequence $A=(A_1,A_2,\\cdots,A_M)$ of length $M$ ($0 \\leq A_i < L$). For each $k=1,2,\\cdots,N$, solve the following problem:\nThere are $k$ red balls numbered from $1$ to $k$ and $k$ blue balls numbered from $1$ to $k$. Now, you will write a real number on each ball in the following way. Here, all random choices are independent.\n\n*   For each $1 \\leq i \\leq k$, the number written on red ball $i$ is $L \\times (i-1)+A_{j_i}$. Here, $j_i$ is an integer chosen uniformly at random from the range between $1$ and $M$ (inclusive).\n    \n*   For each $1 \\leq i \\leq k$, the number written on blue ball $i$ is a **real number** chosen uniformly at random from the range $[0,k \\times L)$.\n    \n\nFind the probability, modulo $998244353$, that the following condition is satisfied after writing numbers on all balls.\n\n*   For any real number $x$ ($0 \\leq x \\leq k \\times L$), \"the number of red balls with a number written that is at most $x$\" $\\geq$ \"the number of blue balls with a number written that is at most $x$\".\n\nDefinition of probability modulo $998244353$It can be proved that the desired probability is always a rational number. Also, under the constraints of this problem, it can be proved that if the desired rational number is represented as an irreducible fraction $\\frac{P}{Q}$, then $Q \\neq 0 \\pmod{998244353}$. Therefore, there uniquely exists an integer $R$ satisfying $R \\times Q \\equiv P \\pmod{998244353}, 0 \\leq R \\lt 998244353$. Output this $R$."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 250000$\n*   $1 \\leq M \\leq 250000$\n*   $0 \\leq A_i < L=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$\n$A_1$ $A_2$ $\\cdots$ $A_M$"},{"iden":"sample input 1","content":"2 1\n50000000"},{"iden":"sample output 1","content":"499122177\n686292993\n\n*   $k=1$: The probability of satisfying the condition is $1/2$.\n*   $k=2$: The probability of satisfying the condition is $5/16$."},{"iden":"sample input 2","content":"3 5\n78682095 25048034 71067122 94666780 1927105"},{"iden":"sample output 2","content":"741897823\n406774904\n435399949"},{"iden":"sample input 3","content":"10 7\n40490214 25131781 2271243 52064315 34467030 27419560 56103210"},{"iden":"sample output 3","content":"457696464\n497746652\n679391958\n742383895\n245278311\n709723420\n729551291\n1911348\n414224424\n650563524"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}