Lýsing

Það eru $n + 1$ hnútar, númeraðir frá $0$ til $n$. Í upphafi ertu í hnúti $0$.

Hver hnútur hefur gátt og teljara, þar sem teljarinn fyrir hnút $p$ (með $0 \le p \le n$) er táknaður sem $c_p$ (í upphafi eru allir $0$). Svið hvers teljara er á milli $0$ og $k - 1$, sem táknar $k$ tegundir af fjarflutningsaðferðum. Þessum fjarflutningsaðferðum er stýrt af fylkinu $t_1, t_2, \dots, t_{k-1}$, eins og lýst er hér að neðan.

Þegar þú ert í einhverjum hnúti $p$ framkvæmir þú eftirfarandi aðgerðir:

1. Ýttu einu sinni á hnapp gáttarinnar og uppfærðu teljarann $c_p$ í $(c_p + 1) \bmod k$.
2. Ef uppfærða gildið uppfyllir $c_p = 0$, fjarflyttu þig í hnút $p + 1$.
3. Annars, ef $p - t_{c_p} \ge 0$, fjarflyttu þig í hnút $p - t_{c_p}$ (sér í lagi, þegar $t_{c_p} = 0$, telst fjarflutningur á sjálfan sig einnig sem einn fjarflutningur).
4. Annars skaltu fara aftur í fyrsta skref og endurtaka skrefin hér að ofan.

Þú stoppar samstundis þegar þú kemur fyrst í hnút $n$ og heldur ekki áfram neinum aðgerðum.

Reiknaðu hversu oft þú notaðir gáttina frá upphafi þar til þú stoppar (þ.e. fjölda vel heppnaðra fjarflutninga), og skilaðu niðurstöðunni módúló $10^9 + 7$.

Inntak

Fyrsta línan í inntakinu inniheldur tvær heiltölur $n$ ($1 \le n \le 10^9$) og $k$ ($2 \le k \le 1000$).

Önnur línan inniheldur $k - 1$ heiltölur, sem tákna $t_1, t_2, \dots, t_{k-1}$. Fyrir sérhvert $i \in [1, k - 1]$ gildir að $0 \le t_i \le \min\{100, n - 1\}$.

Úttak

Prentaðu eina heiltölu sem táknar fjölda skipta sem gáttin var notuð, þar sem niðurstaðan er tekin módúló $10^9 + 7$.

Dæmi

Dæmi 1

2 2
1

4

Dæmi 2

6 3
0 0

18

Dæmi 3

114514 5
28 26 70 27

611437835

Athugasemd

Fyrir fyrsta dæmið:

• Staða teljara allra hnúta er $[0, 0, 0]$, og staðsetningin er í hnúti $0$. Að ýta einu sinni á hnapp gáttarinnar breytir stöðu teljaranna í $[1, 0, 0]$. Þar sem $t_1 = 1$ og $0 - 1 < 0$ á sér enginn fjarflutningur stað, svo að ýta aftur á hnapp gáttarinnar breytir stöðu teljaranna í $[0, 0, 0]$, og þú fjarflyst í hnút $1$.
• Staðsetningin er nú í hnúti $1$. Að ýta einu sinni á hnapp gáttarinnar breytir stöðu teljaranna í $[0, 1, 0]$. Þar sem $t_1 = 1$ og $1 - 1 = 0$ fjarflyst þú í hnút $0$.
• Staðsetningin er nú í hnúti $0$. Að ýta einu sinni á hnapp gáttarinnar breytir stöðu teljaranna í $[1, 1, 0]$. Þar sem $t_1 = 1$ og $0 - 1 < 0$ á sér enginn fjarflutningur stað, svo að ýta aftur á hnapp gáttarinnar breytir stöðu teljaranna í $[0, 1, 0]$, og þú fjarflyst í hnút $1$.
• Staðsetningin er nú í hnúti $1$. Að ýta einu sinni á hnapp gáttarinnar breytir stöðu teljaranna í $[0, 0, 0]$, og þú fjarflyst í hnút $2$. Á þessum tímapunkti stoppar þú samstundis, eftir að hafa framkvæmt alls $4$ fjarflutninga.