分数: 450 点
问题陈述
Aoki,AtCoder Inc. 的员工,本月工资由整数决定 N 和一个序列 A 长度 N 如下。
首先,他被给予 N双面骰子(骰子),显示来自 1 to N 具有相同的概率,并且有一个变量 x=0.
然后,重复以下步骤直至终止。
- 掷骰子一次,让 y 就是结果。
- If x<y,付钱给他 A_y 日元并让 x=y.
- 否则,终止该进程。
青木这个月的工资就是通过这个流程支付的总金额。
求青木本月工资的期望值,取模 998244353.
如何求期望值模 998244353
可以证明,本问题求的期望值始终是有理数。此外,该问题的约束保证如果将寻求的期望值表示为约化分数 \frac yx,那么 x 不能被整除 998244353。 这里,恰好有一个 0\leq z\lt998244353 这样 y\equiv xz\pmod{998244353}。打印此内容 z.约束
- 所有输入均为整数。
- 1 \le N \le 3 \times 10^5
- 0 \le A_i < 998244353
输入
输入由标准输入按以下格式给出:
N A_1 A_2 \dots A_N
输出
打印答案。
示例输入 1
3 3 2 6
示例输出 1
776412280
以下是该过程如何进行的示例。
- 最初, x=0.
- 掷骰子一次,显示 1。自从 0<1,付钱给他 A_1 = 3 日元并让 x=1.
- 掷骰子一次,显示 3。自从 1<3,付钱给他 A_3 = 6 日元并让 x=3.
- 掷骰子一次,显示 1。自从 3 \ge 1,终止进程。
在这种情况下,他这个月的工资是 9 日元。
可以计算出他这个月的工资期望值是 \frac{49}{9} 日元,其表示模数 998244353 is 776412280.
示例输入 2
1 998244352
示例输出 2
998244352
示例输入 3
9 3 14 159 2653 58979 323846 2643383 27950288 419716939
示例输出 3
545252774