問題文

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,000,000,007で割った余りを求めなさい。