某天，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$ 的算式共有 $11$ 個，分別為 0+5, 1+4, 2+3, 3+2, 4+1, 5+0, 5-0, 6-1, 7-2, 8-3, 9-4。

範例 2：算式可以不包含 + 或 -。

範例 5：算式不能以 + 或 - 開頭。