有 $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. 否则，返回步骤 1 并重复上述步骤。

当你首次到达节点 $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

输出样例 1

4

输入样例 2

6 3
0 0

输出样例 2

18

输入样例 3

114514 5
28 26 70 27

输出样例 3

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