Опис

Є $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$ телепортації.