題目描述

有 $n + 1$ 個節點，編號由 $0$ 到 $n$。初始時，你位於節點 $0$。

每個節點都有一個傳送門同一個計數器，其中節點 $p$（$0 \le p \le n$）嘅計數器記為 $c_p$（初始時全部都係 $0$）。每個計數器嘅取值範圍喺 $0$ 到 $k - 1$ 之間，代表 $k$ 種傳送方式。呢啲傳送方式由陣列 $t_1, t_2, \dots, t_{k-1}$ 控制，具體規則如下。

當你位於任意節點 $p$ 嗰陣，你會執行以下操作：

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$ 嗰陣，傳送到自己亦都算作一次傳送）。
4. 否則，返回第一步並重複上述步驟。

當你首次到達節點 $n$ 嗰陣，你會即刻停止，唔再進行任何操作。

計算由開始到停止期間你使用傳送門嘅次數（即係成功傳送嘅次數），並將結果對 $10^9 + 7$ 取模後輸出。

輸入格式

輸入嘅第一行包含兩個整數 $n$（$1 \le n \le 10^9$）同 $k$（$2 \le k \le 1000$）。

第二行包含 $k - 1$ 個整數，代表 $t_1, t_2, \dots, t_{k-1}$。對於任意 $i \in [1, k - 1]$，滿足 $0 \le t_i \le \min\{100, n - 1\}$。

輸出格式

輸出一個整數，代表傳送門被使用嘅次數對 $10^9 + 7$ 取模嘅結果。

樣例

樣例 1

2 2
1

4

樣例 2

6 3
0 0

18

樣例 3

114514 5
28 26 70 27

611437835

提示

對於第一個樣例：

• 所有節點嘅計數器狀態係 $[0, 0, 0]$，而且當前位置喺節點 $0$。撳一次傳送門掣之後，計數器狀態變成 $[1, 0, 0]$。由於 $t_1 = 1$ 同埋 $0 - 1 < 0$，冇發生傳送，因此再撳一次傳送門掣之後，計數器狀態變成 $[0, 0, 0]$，你傳送到節點 $1$。
• 當前位置喺節點 $1$。撳一次傳送門掣之後，計數器狀態變成 $[0, 1, 0]$。由於 $t_1 = 1$ 同埋 $1 - 1 = 0$，你傳送到節點 $0$。
• 當前位置喺節點 $0$。撳一次傳送門掣之後，計數器狀態變成 $[1, 1, 0]$。由於 $t_1 = 1$ 同埋 $0 - 1 < 0$，冇發生傳送，因此再撳一次傳送門掣之後，計數器狀態變成 $[0, 1, 0]$，你傳送到節點 $1$。
• 當前位置喺節點 $1$。撳一次傳送門掣之後，計數器狀態變成 $[0, 0, 0]$，你傳送到節點 $2$。呢個時候，你即刻停止，總共進行咗 $4$ 次傳送。