문제 설명

$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. 포털 버튼을 한 번 눌러 카운터 $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$)가 주어집니다.

둘째 줄에는 $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

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$번의 텔레포트를 수행했습니다.