← 返回题目列表

AtCoder · abc326_e

H. “AtCoder Inc.的工资”的报复

中文机器翻译题面 查看原题

分数: 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