Однажды Куонг внезапно задался вопросом: «Сколько существует выражений, результат вычисления которых равен $N$?»

Куонг с грустью осознал, что если к выражению, результат которого равен $N$, приписать +0 или -0, результат останется прежним. Повторяя эту операцию, можно бесконечно создавать выражения, равные $N$.

Поэтому Куонг добавил ограничение: длина выражения должна быть равна $M$, но и в этом случае он не смог найти ответ. Давайте решим эту задачу за него!

Выражение определяется следующим образом:

• Слагаемое — это строка длиной $1$ и более, состоящая только из цифр 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, которая не начинается с 0. Исключением является само число 0, которое начинается с 0, но при этом является слагаемым.
• Выражение — это строка, содержащая $1$ или более слагаемых, разделенных знаками + или -.

Иначе говоря, выражение — это строка, соответствующая следующему регулярному выражению:

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

Входные данные

В первой строке через пробел заданы $N$ и $M$ ($0 \le N \le 10^5, 1 \le M \le 11$).

Выходные данные

Выведите количество различных выражений длины $M$, результат вычисления которых равен $N$. Так как таких выражений может быть очень много, выведите остаток от деления на $10^9+7$.

Примеры

Входные данные 1

5 3

Выходные данные 1

11

Примечание

Пример 1: Существует $11$ выражений длины $3$, результат которых равен $5$: 0+5, 1+4, 2+3, 3+2, 4+1, 5+0, 5-0, 6-1, 7-2, 8-3, 9-4.

Входные данные 2

123 3

Выходные данные 2

1

Примечание

Пример 2: Выражение может не содержать знаков + или -.

Входные данные 3

100000 5

Выходные данные 3

0

Входные данные 4

0 2

Выходные данные 4

0

Входные данные 5

10 3

Выходные данные 5

9

Примечание

Пример 5: Выражение не может начинаться со знака + или -.