题目描述

给定一个 $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$。

从 $N$ 个计数器中均匀随机选择一个，并将其值设置为 $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$。

样例输入 1

2
0 2

样例输出 1

6

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

下面是该过程的一种可能进展方式。

• 将第一个计数器的值设置为 $0$，然后将其他计数器的值增加 $1$。现在，$(C_1,C_2)=(0,1)$。
• 将第二个计数器的值设置为 $0$，然后将其他计数器的值增加 $1$。现在，$(C_1,C_2)=(1,0)$。
• 将第一个计数器的值设置为 $0$，然后将其他计数器的值增加 $1$。现在，$(C_1,C_2)=(0,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$。

样例输入 2

5
0 1 3 10 1000000000000000000

样例输出 2

874839568