Pewnego dnia Kuong nagle zaczął się zastanawiać: „Ile istnieje wyrażeń, których wynik wynosi $N$?”.

Kuong zdał sobie sprawę ze smutnego faktu, że jeśli do wyrażenia o wyniku $N$ dopiszemy +0 lub -0, wynik nadal będzie wynosił $N$. Powtarzając tę operację, można stworzyć nieskończenie wiele takich wyrażeń.

Dlatego Kuong dodał ograniczenie, że długość wyrażenia musi wynosić dokładnie $M$, ale tym razem nie potrafił znaleźć odpowiedzi. Pomóż mu rozwiązać ten problem!

Wyrażenie jest zdefiniowane w następujący sposób:

• Składnik to ciąg znaków o długości co najmniej $1$, składający się wyłącznie z cyfr 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, który nie zaczyna się od 0. Wyjątkiem jest 0, które zaczyna się od 0, ale jest poprawnym składnikiem.
• Wyrażenie to ciąg znaków zawierający co najmniej jeden składnik, w którym poszczególne składniki są oddzielone znakami + lub -.

Innymi słowy, wyrażenie to ciąg znaków spełniający następujące wyrażenie regularne:

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

Wejście

W pierwszej linii podano dwie liczby całkowite $N$ oraz $M$ oddzielone spacją ($0 \le N \le 10^5, 1 \le M \le 11$).

Wyjście

Wypisz liczbę różnych wyrażeń o długości $M$, których wynik wynosi $N$. Ponieważ liczba ta może być bardzo duża, wypisz wynik modulo $10^9+7$.

Przykład

Wejście 1

5 3

Wyjście 1

11

Uwagi

Przykład 1: Wyrażenia o długości $3$, których wynik wynosi $5$, to 0+5, 1+4, 2+3, 3+2, 4+1, 5+0, 5-0, 6-1, 7-2, 8-3, 9-4 – łącznie $11$ wyrażeń.

Wejście 2

123 3

Wyjście 2

1

Uwagi

Przykład 2: Wyrażenie może nie zawierać znaków + ani -.

Wejście 3

100000 5

Wyjście 3

0

Wejście 4

0 2

Wyjście 4

0

Wejście 5

10 3

Wyjście 5

9

Uwagi

Przykład 5: Wyrażenie nie może zaczynać się od + ani -.