{"problem":{"name":"Stochastic Dominance","description":{"content":"Let $L=10^8$. You 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: There ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":8000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc076_d"},"statements":[{"statement_type":"Markdown","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$.\n\n## Constraints\n\n*   $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.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $M$\n$A_1$ $A_2$ $\\cdots$ $A_M$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc076_d","tags":[],"sample_group":[["2 1\n50000000","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$."],["3 5\n78682095 25048034 71067122 94666780 1927105","741897823\n406774904\n435399949"],["10 7\n40490214 25131781 2271243 52064315 34467030 27419560 56103210","457696464\n497746652\n679391958\n742383895\n245278311\n709723420\n729551291\n1911348\n414224424\n650563524"]],"created_at":"2026-03-03 11:01:14"}}