当前没有测试数据。

E - Sugoroku 3

分值：$500$ 分

问题描述

有 $N$ 个方块，分别称为方块 1 到方块 $N$。你从方块 1 出发。

从方块 1 到方块 $N-1$ 每个方块上都有一个骰子。方块 $i$ 上的骰子标有从 $0$ 到 $A_i$ 的整数，每个整数出现的概率相等。骰子的结果是相互独立的。

直到到达方块 $N$，你将重复在当前所在方块上掷骰子。如果方块 $x$ 上的骰子掷出的整数为 $y$，那么你将移动到方块 $x+y$。

求掷骰子的次数的期望值除以 $998244353$ 的余数。

注释

可以证明所求的期望值一定是一个有理数。另外，如果期望值表示为 $\frac{P}{Q}$，其中 $P$ 和 $Q$ 是互质的整数，则唯一存在整数 $R$，满足 $R \times Q \equiv P\pmod{998244353}$，且 $0 \leq R \lt 998244353$。找出这个 $R$。

约束

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

输入

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

$N$

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

输出

输出答案。

3
1 1

4

期望值为 $4$，因此应输出 $4$。

以下是一种到达方块 $N$ 的可能情况：

• 在方块 1 上掷出 $1$，移动到方块 2。
• 在方块 2 上掷出 $0$，停留在方块 2。
• 在方块 2 上掷出 $1$，移动到方块 3。

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

5
3 1 2 1

332748122