Description

There are $n + 1$ nodes, numbered from $0$ to $n$. Initially, you are at node $0$.

Each node has a portal and a counter, where the counter for node $p$ (with $0 \le p \le n$) is denoted as $c_p$ (initially all are $0$). Each counter's range is between $0$ and $k - 1$, representing $k$ types of teleportation methods. These teleportation methods are controlled by the array $t_1, t_2, \dots, t_{k-1}$, as described below.

When you are at any node $p$, you will perform the following operations:

1. Press the portal button once, updating the counter $c_p$ to $(c_p + 1) \bmod k$.
2. If the updated $c_p = 0$, teleport to node $p + 1$.
3. Otherwise, if $p - t_{c_p} \ge 0$, teleport to node $p - t_{c_p}$ (specifically, when $t_{c_p} = 0$, teleporting to yourself also counts as one teleport).
4. Otherwise, return to step one and repeat the above steps.

You stop immediately when you first reach node $n$ and do not continue any operations.

Calculate the number of times you used the portal from the start until you stop (i.e., the number of successful teleports), and return the result modulo $10^9 + 7$.

Input

The first line of the input contains two integers $n$ ($1 \le n \le 10^9$) and $k$ ($2 \le k \le 1000$).

The second line contains $k - 1$ integers, representing $t_1, t_2, \dots, t_{k-1}$. For any $i \in [1, k - 1]$, it holds that $0 \le t_i \le \min\{100, n - 1\}$.

Output

Output a single integer representing the number of times the portal was used, with the result taken modulo $10^9 + 7$.

Examples

Sample 1

2 2
1

4

Sample 2

6 3
0 0

18

Sample 3

114514 5
28 26 70 27

611437835

Note

For the first example:

• The state of all node counters is $[0, 0, 0]$, and the position is at node $0$. Pressing the portal button once changes the counter state to $[1, 0, 0]$. Since $t_1 = 1$ and $0 - 1 < 0$, no teleport occurs, so pressing the portal button again changes the counter state to $[0, 0, 0]$, and you teleport to node $1$.
• The position is now at node $1$. Pressing the portal button once changes the counter state to $[0, 1, 0]$. Since $t_1 = 1$ and $1 - 1 = 0$, you teleport to node $0$.
• The position is now at node $0$. Pressing the portal button once changes the counter state to $[1, 1, 0]$. Since $t_1 = 1$ and $0 - 1 < 0$, no teleport occurs, so pressing the portal button again changes the counter state to $[0, 1, 0]$, and you teleport to node $1$.
• The position is now at node $1$. Pressing the portal button once changes the counter state to $[0, 0, 0]$, and you teleport to node $2$. At this point, you stop immediately, having made a total of $4$ teleports.