"AtCoder 公司薪资"的复仇

题目描述

AtCoder 公司的员工青木,他这个月的薪资由整数 $N$ 和长度为 $N$ 的序列 $A$ 按如下方式确定。

首先,给他一个等概率显示 $1$ 到 $N$ 的整数的 $N$ 面骰子,以及一个变量 $x=0$。

然后,重复以下步骤直到过程终止。

掷一次骰子,将结果记为 $y$。

如果 $x \lt y$,向他支付 $A_y$ 日元,并令 $x=y$。

否则,过程终止。

青木这个月的薪资就是通过这个过程支付的总金额。

求青木这个月薪资的期望值对 $998244353$ 取模的值。

另外,可以证明本题所求的期望值总是有理数,且本题的约束保证,若将所求期望值表示为既约分数 $\frac{y}{x}$,则 $x$ 不被 $998244353$ 整除。此时,存在唯一的 $0 \le z \lt 998244353$ 满足 $y \equiv xz \pmod{998244353}$。请输出这个 $z$。

输入格式

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

$N$
$A_1$ $A_2$ $\dots$ $A_N$

输出格式

输出答案。

样例

3
3 2 6

776412280

这里给出过程的一个示例。

最初,$x=0$。

掷一次骰子,结果为 $1$。由于 $0 \lt 1$,向他支付 $A_1 = 3$ 日元,并令 $x=1$。

掷一次骰子,结果为 $3$。由于 $1 \lt 3$,向他支付 $A_3 = 6$ 日元,并令 $x=3$。

掷一次骰子,结果为 $1$。由于 $3 \ge 1$,过程终止。

此时,他这个月的薪资为 $9$ 日元。

可以算出,他本月薪资的期望值为 $\frac{49}{9}$ 日元,其对 $998244353$ 取模的表示为 $776412280$。

1
998244352

998244352

9
3 14 159 2653 58979 323846 2643383 27950288 419716939

545252774

数据范围

• 所有输入值均为整数。
• $1 \le N \le 3 \times 10^5$
• $0 \le A_i \lt 998244353$