Beschreibung

Es gibt $n + 1$ Knoten, nummeriert von $0$ bis $n$. Zu Beginn befindest du dich bei Knoten $0$.

Jeder Knoten verfügt über ein Portal und einen Zähler, wobei der Zähler für Knoten $p$ (mit $0 \le p \le n$) als $c_p$ bezeichnet wird (anfangs sind alle $0$). Der Wertebereich jedes Zählers liegt zwischen $0$ und $k - 1$, was $k$ Arten von Teleportationsmethoden darstellt. Diese Teleportationsmethoden werden durch das Array $t_1, t_2, \dots, t_{k-1}$ gesteuert, wie nachfolgend beschrieben.

Wenn du dich bei einem beliebigen Knoten $p$ befindest, führst du die folgenden Operationen aus:

1. Drücke einmal den Portalknopf, wodurch der Zähler $c_p$ auf $(c_p + 1) \bmod k$ aktualisiert wird.
2. Wenn für den aktualisierten Zähler $c_p = 0$ gilt, teleportiere zu Knoten $p + 1$.
3. Andernfalls, wenn $p - t_{c_p} \ge 0$ gilt, teleportiere zu Knoten $p - t_{c_p}$ (insbesondere zählt für $t_{c_p} = 0$ das Teleportieren zu sich selbst ebenfalls als eine Teleportation).
4. Andernfalls kehre zu Schritt eins zurück und wiederhole die obigen Schritte.

Du hältst sofort an, sobald du zum ersten Mal Knoten $n$ erreichst, und führst keine weiteren Operationen mehr aus.

Berechne, wie oft du das Portal vom Start bis zum Anhalten benutzt hast (d. h. die Anzahl der erfolgreichen Teleportationen), und gib das Ergebnis modulo $10^9 + 7$ zurück.

Eingabe

Die erste Zeile der Eingabe enthält zwei ganze Zahlen $n$ ($1 \le n \le 10^9$) und $k$ ($2 \le k \le 1000$).

Die zweite Zeile enthält $k - 1$ ganze Zahlen, die $t_1, t_2, \dots, t_{k-1}$ darstellen. Für jedes $i \in [1, k - 1]$ gilt $0 \le t_i \le \min\{100, n - 1\}$.

Ausgabe

Gib eine einzige ganze Zahl aus, die angibt, wie oft das Portal benutzt wurde, wobei das Ergebnis modulo $10^9 + 7$ genommen wird.

Beispiele

Beispiel 1

2 2
1

4

Beispiel 2

6 3
0 0

18

Beispiel 3

114514 5
28 26 70 27

611437835

Hinweis

Für das erste Beispiel:

• Der Zustand aller Knotenzähler ist $[0, 0, 0]$, und die Position ist bei Knoten $0$. Einmaliges Drücken des Portalknopfes ändert den Zählerzustand auf $[1, 0, 0]$. Da $t_1 = 1$ und $0 - 1 < 0$ gilt, findet keine Teleportation statt; erneutes Drücken des Portalknopfes ändert den Zählerzustand auf $[0, 0, 0]$, und du teleportierst zu Knoten $1$.
• Die Position ist nun bei Knoten $1$. Einmaliges Drücken des Portalknopfes ändert den Zählerzustand auf $[0, 1, 0]$. Da $t_1 = 1$ und $1 - 1 = 0$ gilt, teleportierst du zu Knoten $0$.
• Die Position ist nun bei Knoten $0$. Einmaliges Drücken des Portalknopfes ändert den Zählerzustand auf $[1, 1, 0]$. Da $t_1 = 1$ und $0 - 1 < 0$ gilt, findet keine Teleportation statt; erneutes Drücken des Portalknopfes ändert den Zählerzustand auf $[0, 1, 0]$, und du teleportierst zu Knoten $1$.
• Die Position ist nun bei Knoten $1$. Einmaliges Drücken des Portalknopfes ändert den Zählerzustand auf $[0, 0, 0]$, und du teleportierst zu Knoten $2$. An diesem Punkt hältst du sofort an und hast insgesamt $4$ Teleportationen durchgeführt.