双六 3

题目描述

有 $N$ 个方格,称为方格 $1$ 到方格 $N$。一开始,你在方格 $1$ 上。

方格 $1$ 到方格 $N-1$ 上各放有一个骰子。方格 $i$ 上的骰子会以等概率随机掷出 $0$ 以上 $A_i$ 以下的整数(每次掷骰相互独立)。

在到达方格 $N$ 之前,你不断重复在当前方格上掷骰子,并前进掷出的点数。严格来说,当你在方格 $X$ 上掷出 $Y$ 时,你会移动到方格 $X+Y$。

求掷骰子次数的期望值 $\bmod\ 998244353$。

输入格式

$N$
$A_1$ $A_2$ $\dots$ $A_{N-1}$

输出格式

输出答案。

样例

3
1 1

4

所求期望值为 $4$,因此输出 $4$。

到达方格 $N$ 的流程可以举例如下:

• 在方格 $1$ 掷出 $1$,移动到方格 $2$。
• 在方格 $2$ 掷出 $0$,不移动。
• 在方格 $2$ 掷出 $1$,移动到方格 $3$。

这种情况发生的概率是 $\frac{1}{8}$。

5
3 1 2 1

332748122

数据范围

• $2 \le N \le 2 \times 10^5$
• $1 \le A_i \le N-i(1 \le i \le N-1)$
• 所有输入都是整数。

提示

可以证明所求期望值总是有理数。此外,在该问题的约束下,将该值用互素的 $2$ 个整数 $P$, $Q$ 表示为 $\frac{P}{Q}$ 时,可以证明存在唯一的整数 $R$,使得 $R \times Q \equiv P\pmod{998244353}$ 且 $0 \leq R \lt 998244353$。求出这个 $R$。