{"raw_statement":[{"iden":"problem statement","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)."},{"iden":"notes","content":"It 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$."},{"iden":"constraints","content":"*   $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."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$\n$A_1$ $A_2$ $\\ldots$ $A_N$"},{"iden":"sample input 1","content":"2\n0 2"},{"iden":"sample output 1","content":"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."},{"iden":"sample input 2","content":"5\n0 1 3 10 1000000000000000000"},{"iden":"sample output 2","content":"874839568"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}