問題文

$N$ 個のマス目が左右一列にあり、左から順にマス $1,\ 2,...N$ と呼ぶことにします。また、マス $i$ には整数 $A_i$ が書かれています。

Penguinman は今マス $1$ にいて、マス $N$ に移動しようとしています。

Penguinman はマス $i$ にいるとき、以下の条件のいずれかまたは両方を満たすマス $j\ (i<j≤N)$ に移動することができます。

• $i≡j\ \bmod\ A_i$ である。
• $i+1=j$ である。

Penguinman がマス $N$ に移動する方法は何通りありますか？答えは非常に大きくなることがあるので、$10^9+7$ で割った余りを出力してください。

移動する方法を数えるにあたっては、経由したマスの集合のみを区別するものとします。

注意

時間制限の厳しい問題になっております。

PyPy3 による想定解の AC は確認しておりますが（$900$ms 程度）、同様のコードを Python3 で投げたところ TLE しました。

Python ユーザーの方には PyPy3 による提出を推奨します。

入力

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

• $2≤N≤10^5$
• $1≤A_i≤N$
• 入力は全て整数

出力

最後に改行してください。$\bmod$ を取ることを忘れないでください。

サンプル

3
2 1 1

2

5
5 5 5 5 5

1

10
5 1 9 1 1 3 4 2 1 10

57