Một ngày nọ, Kuong đột nhiên nảy ra thắc mắc: "Có bao nhiêu biểu thức cho kết quả bằng $N$?"

Kuong nhận ra một sự thật đáng buồn là nếu ta thêm +0, -0 vào sau một biểu thức có kết quả là $N$ thì kết quả vẫn là $N$, và nếu cứ lặp lại thao tác này thì ta có thể tạo ra vô số biểu thức có kết quả là $N$.

Vì vậy, Kuong đã thêm vào điều kiện rằng độ dài của biểu thức phải bằng $M$, nhưng lần này cậu ấy vẫn không tìm ra đáp án. Hãy giúp Kuong giải quyết vấn đề này!

Biểu thức được định nghĩa như sau:

• Hạng tử là một chuỗi có độ dài từ $1$ trở lên, chỉ bao gồm các chữ số 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 và không bắt đầu bằng 0. Tuy nhiên, 0 là một trường hợp ngoại lệ, nó bắt đầu bằng 0 nhưng vẫn được coi là một hạng tử.
• Biểu thức là một chuỗi bao gồm $1$ hoặc nhiều hạng tử, trong đó các hạng tử được ngăn cách bởi dấu + hoặc -.

Nói cách khác, biểu thức là một chuỗi thỏa mãn biểu thức chính quy sau:

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

Dữ liệu vào

Dòng đầu tiên chứa $N$ và $M$ cách nhau bởi dấu cách. ($0 \le N \le 10^5, 1 \le M \le 11$)

Dữ liệu ra

In ra số lượng các biểu thức khác nhau có độ dài $M$ và có kết quả bằng $N$. Vì số lượng biểu thức có thể rất lớn, hãy in ra phần dư của kết quả khi chia cho $10^9+7$.

Ví dụ

Dữ liệu vào 1

5 3

Dữ liệu ra 1

11

Ghi chú

Ví dụ 1: Các biểu thức có độ dài $3$ cho kết quả bằng $5$ là 0+5, 1+4, 2+3, 3+2, 4+1, 5+0, 5-0, 6-1, 7-2, 8-3, 9-4, tổng cộng có $11$ biểu thức.

Dữ liệu vào 2

123 3

Dữ liệu ra 2

1

Ghi chú

Ví dụ 2: Biểu thức có thể không chứa dấu + hoặc -.

Dữ liệu vào 3

100000 5

Dữ liệu ra 3

0

Dữ liệu vào 4

0 2

Dữ liệu ra 4

0

Dữ liệu vào 5

10 3

Dữ liệu ra 5

9

Ghi chú

Ví dụ 5: Biểu thức không được bắt đầu bằng dấu + hoặc -.