当前没有测试数据。

Ex - 加1

得分：600分

题目描述

给定一个由$N$个非负整数组成的元组$A=(A_1,A_2,\ldots,A_N)$，其中$A_1=0$且$A_N>0$。

高桥有$N$个计数器，初始时所有计数器的值都是$0$。
他将重复以下操作，直到对于每个$1\leq i\leq N$，第$i$个计数器的值至少为$A_i$。

均匀随机选择一个计数器并将其值设置为$0$。（每次选择都是相互独立的。）
将其它计数器的值增加$1$。

输出高桥重复该操作的次数的期望值，结果对$998244353$取模（参见注释部分）。

注释

可以证明，所求的期望值始终是有限且有理数。此外，在本问题的约束条件下，当该值表示为用两个互质整数$P$和$Q$作为分子和分母的分数$\frac{P}{Q}$时，可以证明存在唯一的整数$R$满足$R \times Q \equiv P\pmod{998244353}$且$0 \leq R \lt 998244353$。请找到这个$R$。

约束

• $2\leq N\leq 2\times 10^5$
• $0=A_1\leq A_2\leq \cdots \leq A_N\leq 10^{18}$
• $A_N>0$
• 输入中的所有值均为整数。

输入

从标准输入读入数据，格式如下：

$N$

$A_1$ $A_2$ $\ldots$ $A_N$

输出

输出高桥重复该操作的次数的期望值，结果对$998244353$取模。

2
0 2

6

令$C_i$表示第$i$个计数器的值。

以下是该过程的一种可能的进展。

• 将第$1$个计数器的值设置为$0$，然后将其它计数器的值增加$1$。现在，$(C_1,C_2)=(0,1)$。
• 将第$2$个计数器的值设置为$0$，然后将其它计数器的值增加$1$。现在，$(C_1,C_2)=(1,0)$。
• 将第$1$个计数器的值设置为$0$，然后将其它计数器的值增加$1$。现在，$(C_1,C_2)=(0,1)$。
• 将第$1$个计数器的值设置为$0$，然后将其它计数器的值增加$1$。现在，$(C_1,C_2)=(0,2)$。

在这种情况下，操作执行了四次。

该过程在恰好执行$1,2,3,4,5,\ldots$次操作后结束的概率分别是$0,\frac{1}{4}, \frac{1}{8}, \frac{1}{8}, \frac{3}{32},\ldots$，因此所求的期望值是$2\times\frac{1}{4}+3\times\frac{1}{8}+4\times\frac{1}{8}+5\times\frac{3}{32}+\dots=6$。 因此，应输出$6$。

5
0 1 3 10 1000000000000000000

874839568