問題文

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

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

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

• $i\equiv jmod{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\le N\le {10}^5$
• $1\le A_i\le N$
• 入力は全て整数

出力

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

サンプル

3
2 1 1

2

5
5 5 5 5 5

1

10
5 1 9 1 1 3 4 2 1 10

57