題目描述

有 $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$ 次傳送。