{"problem":{"name":"Ex - add 1","description":{"content":"You are given a tuple of $N$ non-negative integers $A=(A_1,A_2,\\ldots,A_N)$ such that $A_1=0$ and $A_N>0$. Takahashi has $N$ counters. Initially, the values of all counters are $0$.   He will repeat t","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc270_h"},"statements":[{"statement_type":"Markdown","content":"You are given a tuple of $N$ non-negative integers $A=(A_1,A_2,\\ldots,A_N)$ such that $A_1=0$ and $A_N>0$.\nTakahashi has $N$ counters. Initially, the values of all counters are $0$.  \nHe will repeat the following operation until, for every $1\\leq i\\leq N$, the value of the $i$\\-th counter is at least $A_i$.\n\n> Choose one of the $N$ counters uniformly at random and set its value to $0$. (Each choice is independent of others.)  \n> Increase the values of the **other** counters by $1$.\n\nPrint the expected value of the number of times Takahashi repeats the operation, modulo $998244353$ (see Notes).\n\n## Constraints\n\n*   $2\\leq N\\leq 2\\times 10^5$\n*   $0=A_1\\leq A_2\\leq \\cdots \\leq A_N\\leq 10^{18}$\n*   $A_N>0$\n*   All values in the input are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$\n$A_1$ $A_2$ $\\ldots$ $A_N$\n\n[samples]\n\n## Notes\n\nIt can be proved that the sought expected value is always finite and rational. Additionally, under the Constraints of this problem, when that value is represented as $\\frac{P}{Q}$ using two coprime integers $P$ and $Q$, one can prove that there is a unique integer $R$ such that $R \\times Q \\equiv P\\pmod{998244353}$ and $0 \\leq R \\lt 998244353$. Find this $R$.","is_translate":false,"language":"English"}],"meta":{"iden":"abc270_h","tags":[],"sample_group":[["2\n0 2","6\n\nLet $C_i$ denote the value of the $i$\\-th counter.\nHere is one possible progression of the process.\n\n*   Set the value of the $1$\\-st counter to $0$, and then increase the value of the other counter by $1$. Now, $(C_1,C_2)=(0,1)$.\n*   Set the value of the $2$\\-nd counter to $0$, and then increase the value of the other counter by $1$. Now, $(C_1,C_2)=(1,0)$.\n*   Set the value of the $1$\\-st counter to $0$, and then increase the value of the other counter by $1$. Now, $(C_1,C_2)=(0,1)$.\n*   Set the value of the $1$\\-st counter to $0$, and then increase the value of the other counter by $1$. Now, $(C_1,C_2)=(0,2)$.\n\nIn this case, the operation is performed four times.\nThe probabilities that the process ends after exactly $1,2,3,4,5,\\ldots$ operation(s) are $0,\\frac{1}{4}, \\frac{1}{8}, \\frac{1}{8}, \\frac{3}{32},\\ldots$, respectively, so the sought expected value is $2\\times\\frac{1}{4}+3\\times\\frac{1}{8}+4\\times\\frac{1}{8}+5\\times\\frac{3}{32}+\\dots=6$. Thus, $6$ should be printed."],["5\n0 1 3 10 1000000000000000000","874839568"]],"created_at":"2026-03-03 11:01:13"}}