You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Dice Journey

Problem Statement

There are $N$ $(2 \leq N \leq 2 \times 10^5)$ squares, numbered from $1$ through $N$. You start on square $1$. Each of the squares from $1$ through $N - 1$ has a die on it. The die on square $i$ is labeled with the integers from $0$ through $A_i$, each occurring with equal probability. (Die rolls are independent of each other.) Until you reach square $N$, you will repeat rolling a die on the square you are on. If the die on square $x$ rolls the integer $y$, you go to square $x + y$.

Find the expected value, modulo $998244353$, of the number of times you roll a die.

It can be proved that the sought expected value is always a rational number. Additionally, if that value is represented $\frac{P}{Q}$ using two coprime integers $P$ and $Q$, there is a unique integer $R$ such that $R \times Q = P$ $\pmod{998244353}$ and $0 \leq R < 998244353$. Find this $R$.

INPUT FORMAT (input arrives from the terminal / stdin):

• Line 1: A single integer, $N$.
• Line 2: $N - 1$ integers, $A_i$ $(1 \leq A_i \leq N - i)$ for $1 \leq i \leq N - 1$, separated by spaces.

OUTPUT FORMAT (print output to the terminal / stdout):

• Line 1: A single integer, the expected value modulo $998244353$ of the number of times you roll a die, represented as described in the problem statement.

SAMPLE INPUT 1:

3
1 1

SAMPLE OUTPUT 1:

4

Let's consider one possible sequence of events until we reach Square $N$:

1. You roll a $1$ on Square $1$, which allows you to move to Square $2$.
2. On Square $2$, you roll a $0$, meaning you stay on Square $2$.
3. You roll a $1$ on Square $2$ next, allowing you to move to Square $3$.

This sequence of events occurs with a probability of $\frac14$. It takes $3$ die rolls to reach Square $N$ in this case. However, considering all possible case, the average or expected number of times you roll a die is $4$.

SAMPLE INPUT 2:

5
3 1 2 1

SAMPLE OUTPUT 2:

332748122

SCORING:

• Inputs 3: $1 \leq N \leq 70000$
• Inputs 4-30: No additional constraints.