Problem Statement

There are $N$ squares arranged in a horizontal row, called squares $1,\ 2,...N$ from left to right. Square $i$ has an integer $A_i$ written on it.

Penguinman is currently on square $1$ and wants to move to square $N$.

When Penguinman is on square $i$, he can move to a square $j\ (i<j≤N)$ that satisfies at least one of the following conditions.

• $i≡j\ \bmod\ A_i$.
• $i+1=j$.

In how many ways can Penguinman move to square $N$? Since the answer can be very large, output it modulo $10^9+7$.

When counting the ways to move, two ways are distinguished only by the set of squares they pass through.

Note

This problem has a tight time limit.

We have confirmed that the intended solution gets AC with PyPy3 (in about $900$ms), but similar code submitted with Python3 got TLE.

We recommend that Python users submit with PyPy3.

Input

$N$
$A_1\ A_2\ ...\ A_N$

• $2≤N≤10^5$
• $1≤A_i≤N$
• All inputs are integers.

Output

Print a newline at the end. Do not forget to take the $\bmod$.

Sample

3
2 1 1

2

5
5 5 5 5 5

1

10
5 1 9 1 1 3 4 2 1 10

57