Kuvaus

On $n + 1$ solmua, jotka on numeroitu $0$:sta $n$:ään. Aluksi olet solmussa $0$.

Jokaisessa solmussa on portaali ja laskuri, missä solmun $p$ (kun $0 \le p \le n$) laskuria merkitään $c_p$:llä (aluksi kaikki ovat $0$). Jokaisen laskurin arvoalue on välillä $0$ – $k - 1$, mikä edustaa $k$:ta erilaista teleportaatiomenetelmää. Näitä teleportaatiomenetelmiä ohjaa taulukko $t_1, t_2, \dots, t_{k-1}$ alla kuvatulla tavalla.

Kun olet missä tahansa solmussa $p$, suoritat seuraavat toimenpiteet:

1. Paina portaalin painiketta kerran, jolloin laskurin $c_p$ arvoksi päivittyy $(c_p + 1) \bmod k$.
2. Jos päivitetty $c_p = 0$, teleporttaa solmuun $p + 1$.
3. Muussa tapauksessa, jos $p - t_{c_p} \ge 0$, teleporttaa solmuun $p - t_{c_p}$ (erityisesti kun $t_{c_p} = 0$, teleporttaaminen omaan solmuun lasketaan myös yhdeksi teleporttaukseksi).
4. Muussa tapauksessa palaa vaiheeseen yksi ja toista yllä olevat vaiheet.

Pysähdyt välittömästi, kun saavutat solmun $n$ ensimmäisen kerran, etkä jatka mitään toimenpiteitä.

Laske, kuinka monta kertaa käytit portaalia alusta pysähtymiseen asti (eli onnistuneiden teleporttausten lukumäärä), ja ilmoita tulos modulo $10^9 + 7$.

Syöte

Syötteen ensimmäinen rivi sisältää kaksi kokonaislukua $n$ ($1 \le n \le 10^9$) ja $k$ ($2 \le k \le 1000$).

Toinen rivi sisältää $k - 1$ kokonaislukua, jotka kuvaavat lukuja $t_1, t_2, \dots, t_{k-1}$. Jokaiselle $i \in [1, k - 1]$ pätee $0 \le t_i \le \min\{100, n - 1\}$.

Tuloste

Tulosta yksi kokonaisluku, joka kuvaa portaalin käyttökertojen lukumäärää modulo $10^9 + 7$.

Esimerkit

Esimerkki 1

2 2
1

4

Esimerkki 2

6 3
0 0

18

Esimerkki 3

114514 5
28 26 70 27

611437835

Huomautus

Ensimmäisessä esimerkissä:

• Kaikkien solmujen laskurien tila on $[0, 0, 0]$, ja sijainti on solmussa $0$. Portaalin painikkeen painaminen kerran muuttaa laskurien tilaksi $[1, 0, 0]$. Koska $t_1 = 1$ ja $0 - 1 < 0$, teleporttausta ei tapahdu, joten portaalin painikkeen painaminen uudelleen muuttaa laskurien tilaksi $[0, 0, 0]$, ja teleporttaat solmuun $1$.
• Sijainti on nyt solmussa $1$. Portaalin painikkeen painaminen kerran muuttaa laskurien tilaksi $[0, 1, 0]$. Koska $t_1 = 1$ ja $1 - 1 = 0$, teleporttaat solmuun $0$.
• Sijainti on nyt solmussa $0$. Portaalin painikkeen painaminen kerran muuttaa laskurien tilaksi $[1, 1, 0]$. Koska $t_1 = 1$ ja $0 - 1 < 0$, teleporttausta ei tapahdu, joten portaalin painikkeen painaminen uudelleen muuttaa laskurien tilaksi $[0, 1, 0]$, ja teleporttaat solmuun $1$.
• Sijainti on nyt solmussa $1$. Portaalin painikkeen painaminen kerran muuttaa laskurien tilaksi $[0, 0, 0]$, ja teleporttaat solmuun $2$. Tässä vaiheessa pysähdyt välittömästi tehtyäsi yhteensä $4$ teleporttausta.