Description

Il y a $n + 1$ nœuds, numérotés de $0$ à $n$. Initialement, vous vous trouvez au nœud $0$.

Chaque nœud possède un portail et un compteur, où le compteur du nœud $p$ (avec $0 \le p \le n$) est noté $c_p$ (initialement, tous valent $0$). La valeur de chaque compteur est comprise entre $0$ et $k - 1$, représentant $k$ types de méthodes de téléportation. Ces méthodes de téléportation sont contrôlées par le tableau $t_1, t_2, \dots, t_{k-1}$, comme décrit ci-dessous.

Lorsque vous êtes à un nœud quelconque $p$, vous effectuez les opérations suivantes :

1. Appuyez une fois sur le bouton du portail, ce qui met à jour le compteur $c_p$ à $(c_p + 1) \bmod k$.
2. Si la nouvelle valeur vérifie $c_p = 0$, téléportez-vous au nœud $p + 1$.
3. Sinon, si $p - t_{c_p} \ge 0$, téléportez-vous au nœud $p - t_{c_p}$ (en particulier, lorsque $t_{c_p} = 0$, se téléporter sur soi-même compte également comme une téléportation).
4. Sinon, revenez à la première étape et répétez les étapes ci-dessus.

Vous vous arrêtez immédiatement dès que vous atteignez le nœud $n$ pour la première fois et vous ne poursuivez aucune opération.

Calculez le nombre de fois où vous avez utilisé le portail depuis le début jusqu'à votre arrêt (c'est-à-dire le nombre de téléportations réussies), et renvoyez le résultat modulo $10^9 + 7$.

Entrée

La première ligne de l'entrée contient deux entiers $n$ ($1 \le n \le 10^9$) et $k$ ($2 \le k \le 1000$).

La deuxième ligne contient $k - 1$ entiers, représentant $t_1, t_2, \dots, t_{k-1}$. Pour tout $i \in [1, k - 1]$, on a $0 \le t_i \le \min\{100, n - 1\}$.

Sortie

Affichez un seul entier représentant le nombre de fois où le portail a été utilisé, le résultat étant pris modulo $10^9 + 7$.

Exemples

Exemple 1

2 2
1

4

Exemple 2

6 3
0 0

18

Exemple 3

114514 5
28 26 70 27

611437835

Note

Pour le premier exemple :

• L'état des compteurs de tous les nœuds est $[0, 0, 0]$, et la position est au nœud $0$. Appuyer une fois sur le bouton du portail change l'état des compteurs en $[1, 0, 0]$. Comme $t_1 = 1$ et $0 - 1 < 0$, aucune téléportation n'a lieu ; appuyer à nouveau sur le bouton du portail change l'état des compteurs en $[0, 0, 0]$, et vous vous téléportez au nœud $1$.
• La position est maintenant au nœud $1$. Appuyer une fois sur le bouton du portail change l'état des compteurs en $[0, 1, 0]$. Comme $t_1 = 1$ et $1 - 1 = 0$, vous vous téléportez au nœud $0$.
• La position est maintenant au nœud $0$. Appuyer une fois sur le bouton du portail change l'état des compteurs en $[1, 1, 0]$. Comme $t_1 = 1$ et $0 - 1 < 0$, aucune téléportation n'a lieu ; appuyer à nouveau sur le bouton du portail change l'état des compteurs en $[0, 1, 0]$, et vous vous téléportez au nœud $1$.
• La position est maintenant au nœud $1$. Appuyer une fois sur le bouton du portail change l'état des compteurs en $[0, 0, 0]$, et vous vous téléportez au nœud $2$. À ce moment-là, vous vous arrêtez immédiatement, ayant effectué un total de $4$ téléportations.