Beskrivning

Det finns $n + 1$ noder, numrerade från $0$ till $n$. Från början befinner du dig vid nod $0$.

Varje nod har en portal och en räknare, där räknaren för nod $p$ (med $0 \le p \le n$) betecknas som $c_p$ (från början är alla $0$). Varje räknares intervall ligger mellan $0$ och $k - 1$, vilket representerar $k$ typer av teleporteringsmetoder. Dessa teleporteringsmetoder styrs av arrayen $t_1, t_2, \dots, t_{k-1}$, enligt beskrivningen nedan.

När du befinner dig vid en godtycklig nod $p$ utför du följande operationer:

1. Tryck på portalknappen en gång, vilket uppdaterar räknaren $c_p$ till $(c_p + 1) \bmod k$.
2. Om det uppdaterade värdet uppfyller $c_p = 0$, teleportera till nod $p + 1$.
3. Annars, om $p - t_{c_p} \ge 0$, teleportera till nod $p - t_{c_p}$ (specifikt, när $t_{c_p} = 0$, räknas teleportering till dig själv också som en teleportering).
4. Annars, gå tillbaka till steg ett och upprepa stegen ovan.

Du stannar omedelbart när du för första gången når nod $n$ och fortsätter inte med några operationer.

Beräkna antalet gånger du använde portalen från start tills du stannar (dvs. antalet lyckade teleporteringar), och returnera resultatet modulo $10^9 + 7$.

Indata

Den första raden i indatan innehåller två heltal $n$ ($1 \le n \le 10^9$) och $k$ ($2 \le k \le 1000$).

Den andra raden innehåller $k - 1$ heltal, som representerar $t_1, t_2, \dots, t_{k-1}$. För varje $i \in [1, k - 1]$ gäller att $0 \le t_i \le \min\{100, n - 1\}$.

Utdata

Skriv ut ett enda heltal som representerar antalet gånger portalen användes, med resultatet taget modulo $10^9 + 7$.

Exempel

Exempel 1

2 2
1

4

Exempel 2

6 3
0 0

18

Exempel 3

114514 5
28 26 70 27

611437835

Anmärkning

För det första exemplet:

• Tillståndet för alla nodräknare är $[0, 0, 0]$, och positionen är vid nod $0$. Att trycka på portalknappen en gång ändrar räknartillståndet till $[1, 0, 0]$. Eftersom $t_1 = 1$ och $0 - 1 < 0$ sker ingen teleportering, så att trycka på portalknappen igen ändrar räknartillståndet till $[0, 0, 0]$, och du teleporteras till nod $1$.
• Positionen är nu vid nod $1$. Att trycka på portalknappen en gång ändrar räknartillståndet till $[0, 1, 0]$. Eftersom $t_1 = 1$ och $1 - 1 = 0$ teleporteras du till nod $0$.
• Positionen är nu vid nod $0$. Att trycka på portalknappen en gång ändrar räknartillståndet till $[1, 1, 0]$. Eftersom $t_1 = 1$ och $0 - 1 < 0$ sker ingen teleportering, så att trycka på portalknappen igen ändrar räknartillståndet till $[0, 1, 0]$, och du teleporteras till nod $1$.
• Positionen är nu vid nod $1$. Att trycka på portalknappen en gång ändrar räknartillståndet till $[0, 0, 0]$, och du teleporteras till nod $2$. Vid denna punkt stannar du omedelbart, efter att ha gjort totalt $4$ teleporteringar.