クオンはある日突然、こんな疑問を抱いた。「演算結果が $N$ になる数式はいくつあるのだろうか？」

クオンは、演算結果が $N$ になる数式の後ろに +0 や -0 などを付け加えても演算結果は $N$ のままであるため、この操作を繰り返せば演算結果が $N$ になる数式を無限に作れてしまうという悲しい事実に気づいてしまった。

そこでクオンは、数式の長さが $M$ でなければならないという制約を追加したが、今度は答えを出すことができなかった。皆さんが代わりにこの問題を解いてあげよう！

数式は次のように定義される。

• 項は 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 のみで構成されており、0 で始まらない長さ $1$ 以上の文字列である。ただし 0 は 0 で始まるが、例外的に項である。
• 数式は $1$ つ以上の項を含み、各項が + または - で区切られている文字列である。

言い換えると、数式は次の正規表現を満たす文字列を指す。

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

入力

1 行目に $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: 数式は + や - で始めることはできない。