Descrizione

Ci sono $n + 1$ nodi, numerati da $0$ a $n$. Inizialmente ti trovi nel nodo $0$.

Ogni nodo ha un portale e un contatore, dove il contatore per il nodo $p$ (con $0 \le p \le n$) è indicato con $c_p$ (inizialmente sono tutti pari a $0$). L'intervallo di ciascun contatore è compreso tra $0$ e $k - 1$, e rappresenta $k$ tipi di metodi di teletrasporto. Questi metodi di teletrasporto sono controllati dall'array $t_1, t_2, \dots, t_{k-1}$, come descritto di seguito.

Quando ti trovi in un qualsiasi nodo $p$, esegui le seguenti operazioni:

1. Premi una volta il pulsante del portale, aggiornando il contatore $c_p$ a $(c_p + 1) \bmod k$.
2. Se il valore aggiornato soddisfa $c_p = 0$, teletrasportati al nodo $p + 1$.
3. Altrimenti, se $p - t_{c_p} \ge 0$, teletrasportati al nodo $p - t_{c_p}$ (in particolare, quando $t_{c_p} = 0$, teletrasportarsi su sé stessi conta comunque come un teletrasporto).
4. Altrimenti, torna al passo uno e ripeti i passi precedenti.

Ti fermi immediatamente non appena raggiungi per la prima volta il nodo $n$ e non prosegui con alcuna operazione.

Calcola il numero di volte in cui hai utilizzato il portale dall'inizio fino all'arresto (ovvero il numero di teletrasporti effettuati con successo), e restituisci il risultato modulo $10^9 + 7$.

Input

La prima riga dell'input contiene due interi $n$ ($1 \le n \le 10^9$) e $k$ ($2 \le k \le 1000$).

La seconda riga contiene $k - 1$ interi, che rappresentano $t_1, t_2, \dots, t_{k-1}$. Per ogni $i \in [1, k - 1]$, vale $0 \le t_i \le \min\{100, n - 1\}$.

Output

Stampa un singolo intero che rappresenta il numero di volte in cui è stato utilizzato il portale, con il risultato calcolato modulo $10^9 + 7$.

Esempi

Esempio 1

2 2
1

4

Esempio 2

6 3
0 0

18

Esempio 3

114514 5
28 26 70 27

611437835

Nota

Per il primo esempio:

• Lo stato dei contatori di tutti i nodi è $[0, 0, 0]$, e la posizione è nel nodo $0$. Premendo una volta il pulsante del portale lo stato dei contatori diventa $[1, 0, 0]$. Poiché $t_1 = 1$ e $0 - 1 < 0$, non avviene alcun teletrasporto, quindi premendo nuovamente il pulsante del portale lo stato dei contatori diventa $[0, 0, 0]$, e ti teletrasporti al nodo $1$.
• La posizione è ora nel nodo $1$. Premendo una volta il pulsante del portale lo stato dei contatori diventa $[0, 1, 0]$. Poiché $t_1 = 1$ e $1 - 1 = 0$, ti teletrasporti al nodo $0$.
• La posizione è ora nel nodo $0$. Premendo una volta il pulsante del portale lo stato dei contatori diventa $[1, 1, 0]$. Poiché $t_1 = 1$ e $0 - 1 < 0$, non avviene alcun teletrasporto, quindi premendo nuovamente il pulsante del portale lo stato dei contatori diventa $[0, 1, 0]$, e ti teletrasporti al nodo $1$.
• La posizione è ora nel nodo $1$. Premendo una volta il pulsante del portale lo stato dei contatori diventa $[0, 0, 0]$, e ti teletrasporti al nodo $2$. A questo punto ti fermi immediatamente, avendo effettuato un totale di $4$ teletrasporti.