Beskrivelse

Det er $n + 1$ noder, nummerert fra $0$ til $n$. Til å begynne med er du ved node $0$.

Hver node har en portal og en teller, der telleren for node $p$ (med $0 \le p \le n$) betegnes som $c_p$ (til å begynne med er alle $0$). Hver tellers verdiområde er mellom $0$ og $k - 1$, som representerer $k$ typer teleporteringsmetoder. Disse teleporteringsmetodene styres av arrayen $t_1, t_2, \dots, t_{k-1}$, som beskrevet nedenfor.

Når du er ved en hvilken som helst node $p$, utfører du følgende operasjoner:

1. Trykk én gang på portalknappen, slik at telleren $c_p$ oppdateres til $(c_p + 1) \bmod k$.
2. Hvis den oppdaterte $c_p = 0$, teleporter til node $p + 1$.
3. Ellers, hvis $p - t_{c_p} \ge 0$, teleporter til node $p - t_{c_p}$ (spesifikt, når $t_{c_p} = 0$, teller teleportering til deg selv også som én teleportering).
4. Ellers, gå tilbake til steg én og gjenta stegene ovenfor.

Du stopper umiddelbart når du for første gang når node $n$, og fortsetter ikke med noen operasjoner.

Beregn antallet ganger du brukte portalen fra start til du stopper (dvs. antallet vellykkede teleporteringer), og returner resultatet modulo $10^9 + 7$.

Inndata

Den første linjen av inndataene inneholder to heltall $n$ ($1 \le n \le 10^9$) og $k$ ($2 \le k \le 1000$).

Den andre linjen inneholder $k - 1$ heltall, som representerer $t_1, t_2, \dots, t_{k-1}$. For enhver $i \in [1, k - 1]$ gjelder det at $0 \le t_i \le \min\{100, n - 1\}$.

Utdata

Skriv ut et enkelt heltall som representerer antallet ganger portalen ble brukt, med resultatet tatt modulo $10^9 + 7$.

Eksempler

Eksempel 1

2 2
1

4

Eksempel 2

6 3
0 0

18

Eksempel 3

114514 5
28 26 70 27

611437835

Merk

For det første eksempelet:

• Tilstanden til alle nodetellerne er $[0, 0, 0]$, og posisjonen er ved node $0$. Å trykke én gang på portalknappen endrer tellertilstanden til $[1, 0, 0]$. Siden $t_1 = 1$ og $0 - 1 < 0$, skjer det ingen teleportering, så å trykke på portalknappen igjen endrer tellertilstanden til $[0, 0, 0]$, og du teleporterer til node $1$.
• Posisjonen er nå ved node $1$. Å trykke én gang på portalknappen endrer tellertilstanden til $[0, 1, 0]$. Siden $t_1 = 1$ og $1 - 1 = 0$, teleporterer du til node $0$.
• Posisjonen er nå ved node $0$. Å trykke én gang på portalknappen endrer tellertilstanden til $[1, 1, 0]$. Siden $t_1 = 1$ og $0 - 1 < 0$, skjer det ingen teleportering, så å trykke på portalknappen igjen endrer tellertilstanden til $[0, 1, 0]$, og du teleporterer til node $1$.
• Posisjonen er nå ved node $1$. Å trykke én gang på portalknappen endrer tellertilstanden til $[0, 0, 0]$, og du teleporterer til node $2$. På dette tidspunktet stopper du umiddelbart, etter å ha utført totalt $4$ teleporteringer.