Interstellar Transmissions

Task

After reading about the ambitious SETI program, William decided to join the project and build an array of $N$ radios for interstellar transmissions in his garage. However, the array has not received any extraterrestrial message yet, fact that William blamed to the phenomenon of interference.

In particular, William noticed that whenever the $i$-th radio is turned on, $V_i$ of the radios on its left (that is, radios $j = i-V_i \ldots i-1$) receive disturbed signals and are not usable. Fortunately, no interfering signals are received by radios on the right (that is, with $j > i$). In order to plan his next experiment avoiding interferences, William now needs to select a subset of his radios avoiding interferences, that is, such that if radio $i$ is turned on then all radios between $i-V_i$ and $i-1$ are turned off.

Help William plan his next experiment, by counting the number of subsets of radios avoiding interferences modulo $10^9 + 7$.

Input data

The first line contains the only integer $N$. The second line contains $N$ integers $V_i$.

Output data

You need to write a single line with an integer: the number of valid subsets of radios modulo $10^9 + 7$.

Constraints and clarifications

• $1 \le N \le 1\,000\,000$.
• $0 \le V_i \le i$ for each $i=0\ldots N-1$.

Example 1

stdin

3
0 0 0

stdout

8

Explanation

In the first sample case, there is no interference thus all $8$ subsets of the three radios are valid.

Example 2

stdin

6
0 1 2 3 2 1

stdout

13

Explanation

In the second sample case, the $13$ valid subsets are the following: