有一天，Kuong 突然产生了一个好奇：“有多少个算术表达式的计算结果为 $N$？”

Kuong 意识到一个悲伤的事实：如果一个表达式的计算结果为 $N$，那么在它后面接上 +0 或 -0 等，结果仍然是 $N$。通过重复这种操作，可以无限地构造出结果为 $N$ 的表达式。

因此，Kuong 增加了一个限制：表达式的长度必须为 $M$。但这一次他依然无法得出答案。请你来帮他解决这个问题！

表达式定义如下：

• 项是由 0、1、2、3、4、5、6、7、8、9 组成的长度至少为 $1$ 的字符串，且不能以 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

样例输入 2

123 3

样例输出 2

1

样例输入 3

100000 5

样例输出 3

0

样例输入 4

0 2

样例输出 4

0

样例输入 5

10 3

样例输出 5

9

说明

样例 1：长度为 $3$ 且计算结果为 $5$ 的表达式有 0+5, 1+4, 2+3, 3+2, 4+1, 5+0, 5-0, 6-1, 7-2, 8-3, 9-4，共 $11$ 个。

样例 2：表达式可以不包含 + 或 -。

样例 5：表达式不能以 + 或 - 开头。