Описание

Имеется $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$ телепортации.