AT_s8pc_2_c 何通りの分割方法がある？

[problemUrl]: https://atcoder.jp/contests/s8pc-2/tasks/s8pc_2_c $ square1001 $の部分文字列である「$ 1001 $」は、各位の数字の和が$ 1+0+0+1=2 $と非常に少なく、 しかも「1001」を分割しても{$ 1,0,01 $}や{$ 1,001 $}のようにすると和がそれぞれ$ 1+0+1=2,1+1=2 $と非常に少なくなります。 $ 1001 $はとても不思議な数です。それについて、彼は考えてみることにしました。 整数$ n $を分割するとき、その和が$ D $以下にならなければなりません。 ここでいう「分割」の定義は以下のようになります。 - 整数$ N $を文字列と考えられる。これを$ S $と置く。 - $ S $をいくつかのパーツに分ける。 - 例えば「$ "1234567" $」だと{$ "1","234567" $}や{$ "12","34","56","7" $}や{$ "1234567" $}など、というように分けることができる。 - 分けたパーツをそれぞれ数字としてとらえるようにする。 - 例えば、"1234"は$ 1234 $という数字ととらえることができる。 - ただし、各パーツは$ 0 $から始まってもよい。 例えば、「1355」を和が50以下になるように分割する方法は、以下の$ 3 $通りがあります。 分割方法合計1+3+5+51413+5+5231+35+541何通りの分け方があるか数え上げましょう。$ 1,000,000,007 $で割った余りを求めなさい。 - 問題文中の例と同じである。 - 以下の5通りの条件を満たす分け方がある。 分割方法合計2+4+3+91824+3+9362+4+39452+43+95424+3963

入力は以下の形式で標準入力から与えられる。 > $ N $ $ D $ - $ 1 $ 行目には、分割されるもののもととなる整数 $ N $ が与えられる。 - $ 2 $ 行目には、数の合計の上限 $ D $が与えられる。

出力は以下の形式で標準出力に従うこと。 - 分割の通り数を$ 1,000,000,007 $で割った余りを $ 1 $ 行で出力せよ。

### 制約 - $ 1≦N≦{10}^{100} $ - $ 1≦D≦100,000 $ ### 小課題 小課題 $ 1 $ \[ $ 10 $ 点 \] - 解は全て$ 1 $通り以下である。 小課題 $ 2 $ \[ $ 30 $ 点 \] - $ 1≦N≦10,000,000,000 $を満たす。 小課題 $ 3 $ \[ $ 60 $ 点 \] - 追加の制約はない。