Opis problemu

Danych jest $n + 1$ węzłów, ponumerowanych od $0$ do $n$. Początkowo znajdujesz się w węźle $0$.

Każdy węzeł posiada portal oraz licznik, przy czym licznik dla węzła $p$ (gdzie $0 \le p \le n$) oznaczamy jako $c_p$ (początkowo wszystkie wynoszą $0$). Zakres każdego licznika to przedział od $0$ do $k - 1$, co odpowiada $k$ rodzajom metod teleportacji. Te metody teleportacji są sterowane przez tablicę $t_1, t_2, \dots, t_{k-1}$, jak opisano poniżej.

Będąc w dowolnym węźle $p$, wykonujesz następujące operacje:

1. Naciśnij raz przycisk portalu, aktualizując licznik $c_p$ do wartości $(c_p + 1) \bmod k$.
2. Jeśli zaktualizowany licznik spełnia $c_p = 0$, teleportuj się do węzła $p + 1$.
3. W przeciwnym razie, jeśli $p - t_{c_p} \ge 0$, teleportuj się do węzła $p - t_{c_p}$ (w szczególności, gdy $t_{c_p} = 0$, teleportacja do samego siebie również liczy się jako jedna teleportacja).
4. W przeciwnym razie wróć do kroku pierwszego i powtórz powyższe kroki.

Zatrzymujesz się natychmiast, gdy po raz pierwszy dotrzesz do węzła $n$, i nie wykonujesz już żadnych dalszych operacji.

Oblicz, ile razy użyłeś portalu od początku aż do zatrzymania się (tj. liczbę udanych teleportacji), i zwróć wynik modulo $10^9 + 7$.

Wejście

Pierwszy wiersz wejścia zawiera dwie liczby całkowite $n$ ($1 \le n \le 10^9$) oraz $k$ ($2 \le k \le 1000$).

Drugi wiersz zawiera $k - 1$ liczb całkowitych, reprezentujących $t_1, t_2, \dots, t_{k-1}$. Dla każdego $i \in [1, k - 1]$ zachodzi $0 \le t_i \le \min\{100, n - 1\}$.

Wyjście

Wypisz jedną liczbę całkowitą oznaczającą liczbę użyć portalu, z wynikiem wziętym modulo $10^9 + 7$.

Przykłady

Przykład 1

2 2
1

4

Przykład 2

6 3
0 0

18

Przykład 3

114514 5
28 26 70 27

611437835

Uwaga

Dla pierwszego przykładu:

• Stan liczników wszystkich węzłów wynosi $[0, 0, 0]$, a pozycja to węzeł $0$. Jednokrotne naciśnięcie przycisku portalu zmienia stan liczników na $[1, 0, 0]$. Ponieważ $t_1 = 1$ oraz $0 - 1 < 0$, teleportacja nie następuje, więc ponowne naciśnięcie przycisku portalu zmienia stan liczników na $[0, 0, 0]$ i teleportujesz się do węzła $1$.
• Pozycja to teraz węzeł $1$. Jednokrotne naciśnięcie przycisku portalu zmienia stan liczników na $[0, 1, 0]$. Ponieważ $t_1 = 1$ oraz $1 - 1 = 0$, teleportujesz się do węzła $0$.
• Pozycja to teraz węzeł $0$. Jednokrotne naciśnięcie przycisku portalu zmienia stan liczników na $[1, 1, 0]$. Ponieważ $t_1 = 1$ oraz $0 - 1 < 0$, teleportacja nie następuje, więc ponowne naciśnięcie przycisku portalu zmienia stan liczników na $[0, 1, 0]$ i teleportujesz się do węzła $1$.
• Pozycja to teraz węzeł $1$. Jednokrotne naciśnięcie przycisku portalu zmienia stan liczników na $[0, 0, 0]$ i teleportujesz się do węzła $2$. W tym momencie natychmiast się zatrzymujesz, wykonawszy łącznie $4$ teleportacje.