Te dan una secuencia de n dígitos decimales. La secuencia necesita ser particionadas en una o mas secuencias contiguas tal que cuando esta subsecuencia cuando es interpretada como un numero decimal es divisible por m.

Su tarea es listar estas particiones. Dos particiones son diferentes si las ubicaciones de la subsecuencia son diferentes.

En el ejemplo nos piden las secuencias que son divisibles por 3 de la secuencia 12345.
Estas secuencias se obtienen dividiendo la secuencia en 12, 3 y 45.

El total de secuencias que se pueden formar son: 12,123,12345,345 totalizando 4 secuencias.

Si la la cadena completa no es múltiplo de m muestre 0.

La entrada consiste de dos lineas. La primera linea contiene un numero entero $ 2 \leq M \leq 10^9$.
La segunda linea contiene una cadena de dígitos con $2 \leq n \leq 300000$ caracteres.

En la salida escriba cuantas de estas cadenas se pueden armar, imprima el resultado modulo $10^9+7$