C - 何通りの分割方法がある? Editorial /

Time Limit: 5 sec / Memory Limit: 256 MB

問題文

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+514
13+5+523
1+35+541

何通りの分け方があるか数え上げましょう。1,000,000,007で割った余りを求めなさい。

入力

入力は以下の形式で標準入力から与えられる。

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 点 ]

  • 追加の制約はない。

入力例1

1355
50

出力例1

3
  • 問題文中の例と同じである。

入力例2

2439
100

出力例2

5
  • 以下の5通りの条件を満たす分け方がある。
分割方法合計
2+4+3+918
24+3+936
2+4+3945
2+43+954
24+3963

入力例3

1225
20

出力例3

2

入力例4

123456
10000

出力例4

29

問題文担当者:E869120