Descripción

Hay $n + 1$ nodos, numerados de $0$ a $n$. Inicialmente, te encuentras en el nodo $0$.

Cada nodo tiene un portal y un contador, donde el contador para el nodo $p$ (con $0 \le p \le n$) se denota como $c_p$ (inicialmente todos son $0$). El rango de cada contador está entre $0$ y $k - 1$, lo que representa $k$ tipos de métodos de teletransportación. Estos métodos de teletransportación están controlados por el arreglo $t_1, t_2, \dots, t_{k-1}$, como se describe a continuación.

Cuando estés en cualquier nodo $p$, realizarás las siguientes operaciones:

1. Presiona el botón del portal una vez, actualizando el contador $c_p$ a $(c_p + 1) \bmod k$.
2. Si el valor actualizado cumple $c_p = 0$, teletranspórtate al nodo $p + 1$.
3. De lo contrario, si $p - t_{c_p} \ge 0$, teletranspórtate al nodo $p - t_{c_p}$ (específicamente, cuando $t_{c_p} = 0$, teletransportarte a ti mismo también cuenta como una teletransportación).
4. De lo contrario, regresa al paso uno y repite los pasos anteriores.

Te detienes inmediatamente cuando alcanzas por primera vez el nodo $n$ y no continúas con ninguna operación.

Calcula la cantidad de veces que usaste el portal desde el inicio hasta que te detienes (es decir, el número de teletransportaciones exitosas), y devuelve el resultado módulo $10^9 + 7$.

Entrada

La primera línea de la entrada contiene dos enteros $n$ ($1 \le n \le 10^9$) y $k$ ($2 \le k \le 1000$).

La segunda línea contiene $k - 1$ enteros, que representan $t_1, t_2, \dots, t_{k-1}$. Para cualquier $i \in [1, k - 1]$, se cumple que $0 \le t_i \le \min\{100, n - 1\}$.

Salida

Imprime un solo entero que represente la cantidad de veces que se usó el portal, tomando el resultado módulo $10^9 + 7$.

Ejemplos

Ejemplo 1

2 2
1

4

Ejemplo 2

6 3
0 0

18

Ejemplo 3

114514 5
28 26 70 27

611437835

Nota

Para el primer ejemplo:

• El estado de los contadores de todos los nodos es $[0, 0, 0]$, y la posición está en el nodo $0$. Presionar el botón del portal una vez cambia el estado de los contadores a $[1, 0, 0]$. Como $t_1 = 1$ y $0 - 1 < 0$, no ocurre ninguna teletransportación, por lo que presionar el botón del portal nuevamente cambia el estado de los contadores a $[0, 0, 0]$, y te teletransportas al nodo $1$.
• La posición está ahora en el nodo $1$. Presionar el botón del portal una vez cambia el estado de los contadores a $[0, 1, 0]$. Como $t_1 = 1$ y $1 - 1 = 0$, te teletransportas al nodo $0$.
• La posición está ahora en el nodo $0$. Presionar el botón del portal una vez cambia el estado de los contadores a $[1, 1, 0]$. Como $t_1 = 1$ y $0 - 1 < 0$, no ocurre ninguna teletransportación, por lo que presionar el botón del portal nuevamente cambia el estado de los contadores a $[0, 1, 0]$, y te teletransportas al nodo $1$.
• La posición está ahora en el nodo $1$. Presionar el botón del portal una vez cambia el estado de los contadores a $[0, 0, 0]$, y te teletransportas al nodo $2$. En este punto, te detienes inmediatamente, habiendo realizado un total de $4$ teletransportaciones.