加 1

题目描述

给定一个由 $N$ 个非负整数组成的元组 $A=(A_1,A_2,\ldots,A_N)$,满足 $A_1=0$ 且 $A_N\gt 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$。

输入格式

输入按以下格式从标准输入给出:

$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

数据范围

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