Kuong de repente se preguntó: "¿Cuántas expresiones matemáticas existen cuyo resultado sea $N$?"

Kuong se dio cuenta de la triste realidad de que, dado que añadir +0, -0, etc., al final de una expresión cuyo resultado es $N$ mantiene el resultado en $N$, al repetir este proceso se pueden crear infinitas expresiones.

Por lo tanto, Kuong añadió la restricción de que la longitud de la expresión debe ser exactamente $M$, pero esta vez no pudo encontrar la respuesta. ¡Ayudémosle a resolver este problema!

Una expresión se define de la siguiente manera:

• Un término es una cadena de longitud $1$ o más, compuesta solo por 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, que no comienza con 0. Sin embargo, 0 es una excepción y se considera un término aunque comience con 0.
• Una expresión es una cadena que contiene $1$ o más términos, donde cada término está separado por + o -.

En otras palabras, una expresión es una cadena que satisface la siguiente expresión regular:

• (([1-9][0-9]*|'0')[+-]))*([1-9][0-9]*|'0')

La primera línea contiene $N$ y $M$ separados por un espacio. ($0 \le N \le 10^5, 1 \le M \le 11$)

Imprima el número de expresiones distintas de longitud $M$ cuyo resultado sea $N$. Dado que puede haber muchas de estas expresiones, imprima el resultado módulo $10^9+7$.

Ejemplos

Entrada 1

5 3

Salida 1

11

Entrada 2

123 3

Salida 2

1

Entrada 3

100000 5

Salida 3

0

Entrada 4

0 2

Salida 4

0

Entrada 5

10 3

Salida 5

9

Nota

• Ejemplo 1: Las expresiones de longitud $3$ cuyo resultado es $5$ son 0+5, 1+4, 2+3, 3+2, 4+1, 5+0, 5-0, 6-1, 7-2, 8-3, 9-4, en total $11$.
• Ejemplo 2: Las expresiones pueden no contener + o -.
• Ejemplo 5: Las expresiones no pueden comenzar con + o -.