Problema número 554

Escaleranos

Tiempo máximo: 1,000-2,000 sMemoria máxima: 4096 KiB
Vista cercana de una escalera, con los pies de una persona subiendo

Los habitantes de Escalera son famosos por su capacidad de subir de golpe varios peldaños de una escalera. Además les gusta especializarse en subir un número determinado de peldaños. Juan, por ejemplo, está especializado en subir 1, 3 o 5 peldaños en cada paso (lo que representamos mediante la lista [1, 3, 5]). En esta lista de peldaños siempre aparecerá el 1 en primer lugar, pues todos los escaleranos son capaces de subir los peldaños de uno en uno.

Así las cosas nos surge la curiosidad de saber, por ejemplo, de cuántas maneras distintas podría subir una escalera de 10 peldaños un escalerano especializado en subir [1, 3, 5] peldaños. De forma más general, si un escalerano se especializa en subir [p1=1, p2, ..., pk] peldaños, ¿de cuántas maneras diferentes podrá subir una escalera de n peldaños llegando arriba de forma exacta?

Entrada

La entrada está formada por distintos casos de prueba, uno por línea. Cada caso de prueba contiene un primer número entero 1 ≤ n ≤ 100 con el número total de peldaños de una cierta escalera. A continuación hay un segundo número entero 1 ≤ k ≤ 10 con el número de diferentes peldaños que un escalerano puede subir de golpe. Finalmente hay k números enteros p1 = 1,...,pk con los valores de dichos números de peldaños. Se cumple que todos los pi son distintos entre sí y menores o iguales a n.

El final de la entrada se indica con una línea que empieza con un 0 y que no debe procesarse.

Salida

Para cada caso de prueba se escribirá una línea con el número de formas diferentes en las que el escalerano puede subir la escalera, llegando al último peldaño de forma exacta. Como el resultado puede ser muy grande se dará el resto que queda tras dividir el número total entre 1.000.000.007 (109+7).

Entrada de ejemplo

5 2 1 3
5 2 1 4 
5 2 1 5 
5 3 1 3 2
3 2 1 4 
0

Salida de ejemplo

4
3
2
13
1