Un jour, Kuong s'est soudainement posé la question suivante : « Combien existe-t-il d'expressions mathématiques dont le résultat est $N$ ? »

Kuong a réalisé avec tristesse qu'en ajoutant +0, -0, etc., à la fin d'une expression dont le résultat est $N$, on obtient toujours $N$, ce qui signifie qu'il est possible de créer une infinité d'expressions dont le résultat est $N$ en répétant cette opération.

Il a donc ajouté la contrainte que la longueur de l'expression doit être exactement $M$, mais il n'a pas réussi à trouver la réponse. Aidons-le à résoudre ce problème !

Une expression est définie comme suit :

• Un terme est une chaîne de caractères de longueur $1$ ou plus, composée uniquement de 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, et ne commençant pas par 0. Cependant, 0 est une exception et est considéré comme un terme bien qu'il commence par 0.
• Une expression est une chaîne de caractères contenant au moins un terme, où chaque terme est séparé par + ou -.

En d'autres termes, une expression est une chaîne de caractères satisfaisant l'expression régulière suivante :

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

Entrée

La première ligne contient $N$ et $M$ séparés par un espace. ($0 \le N \le 10^5, 1 \le M \le 11$)

Sortie

Affichez le nombre d'expressions distinctes de longueur $M$ dont le résultat est $N$. Comme ce nombre peut être très grand, affichez le résultat modulo $10^9+7$.

Exemples

Entrée 1

5 3

Sortie 1

11

Remarque

Exemple 1 : Les expressions de longueur $3$ dont le résultat est $5$ sont 0+5, 1+4, 2+3, 3+2, 4+1, 5+0, 5-0, 6-1, 7-2, 8-3, 9-4, soit $11$ expressions au total.

Entrée 2

123 3

Sortie 2

1

Remarque

Exemple 2 : Une expression peut ne pas contenir de + ou de -.

Entrée 3

100000 5

Sortie 3

0

Entrée 4

0 2

Sortie 4

0

Entrée 5

10 3

Sortie 5

9

Remarque

Exemple 5 : Une expression ne peut pas commencer par + ou -.