問題文

$0$ から $n$ までの番号がついた $n + 1$ 個のノードがあります。最初、あなたはノード $0$ にいます。

各ノードにはポータルとカウンターがあり、ノード $p$ ($0 \le p \le n$) のカウンターを $c_p$ と表します（初期状態ではすべて $0$ です）。各カウンターの値の範囲は $0$ から $k - 1$ までであり、$k$ 種類のテレポート方法を表しています。これらのテレポート方法は、以下に示すように配列 $t_1, t_2, \dots, t_{k-1}$ によって制御されます。

任意のノード $p$ にいるとき、あなたは以下の操作を行います：

1. ポータルのボタンを 1 回押し、カウンター $c_p$ を $(c_p + 1) \bmod k$ に更新する。
2. 更新後の $c_p = 0$ であれば、ノード $p + 1$ へテレポートする。
3. そうでない場合、もし $p - t_{c_p} \ge 0$ であれば、ノード $p - t_{c_p}$ へテレポートする（特に、$t_{c_p} = 0$ のとき、自分自身へのテレポートも 1 回のテレポートとして数える）。
4. そうでない場合、ステップ 1 に戻り、上記のステップを繰り返す。

初めてノード $n$ に到達した時点で直ちに停止し、それ以上の操作は行いません。

開始から停止するまでにポータルを使用した回数（すなわち、成功したテレポートの回数）を計算し、その結果を $10^9 + 7$ で割った余りを求めてください。

入力

入力の 1 行目には、2 つの整数 $n$ ($1 \le n \le 10^9$) と $k$ ($2 \le k \le 1000$) が与えられます。

2 行目には、$t_1, t_2, \dots, t_{k-1}$ を表す $k - 1$ 個の整数が与えられます。任意の $i \in [1, k - 1]$ について、$0 \le t_i \le \min\{100, n - 1\}$ が成り立ちます。

出力

ポータルが使用された回数を $10^9 + 7$ で割った余りを表す 1 つの整数を出力してください。

例

サンプル 1

2 2
1

4

サンプル 2

6 3
0 0

18

サンプル 3

114514 5
28 26 70 27

611437835

注記

1 番目の例について：

• すべてのノードのカウンターの状態は $[0, 0, 0]$ であり、現在位置はノード $0$ です。ポータルのボタンを 1 回押すと、カウンターの状態は $[1, 0, 0]$ に変わります。$t_1 = 1$ かつ $0 - 1 < 0$ なのでテレポートは発生せず、もう一度ポータルのボタンを押すとカウンターの状態は $[0, 0, 0]$ に変わり、ノード $1$ へテレポートします。
• 現在位置はノード $1$ です。ポータルのボタンを 1 回押すと、カウンターの状態は $[0, 1, 0]$ に変わります。$t_1 = 1$ かつ $1 - 1 = 0$ なので、ノード $0$ へテレポートします。
• 現在位置はノード $0$ です。ポータルのボタンを 1 回押すと、カウンターの状態は $[1, 1, 0]$ に変わります。$t_1 = 1$ かつ $0 - 1 < 0$ なのでテレポートは発生せず、もう一度ポータルのボタンを押すとカウンターの状態は $[0, 1, 0]$ に変わり、ノード $1$ へテレポートします。
• 現在位置はノード $1$ です。ポータルのボタンを 1 回押すと、カウンターの状態は $[0, 0, 0]$ に変わり、ノード $2$ へテレポートします。この時点で直ちに停止し、合計で $4$ 回のテレポートを行ったことになります。