AT_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+5	14
13+5+5	23
135+5	140

请计算有多少种分割方式，使得各部分数字之和不超过 $ D $。答案对 $ 1,000,000,007 $ 取模。

• 与题目中的例子相同。

• 满足以下 $ 5 $ 种条件的分割方式：

分割方式	合计
2+4+3+9	18
24+3+9	36
2+4+39	45
2+43+9	54
24+39	63

输入为以下格式，从标准输入读取。

$ N $ $ D $

• 第 $ 1 $ 行给出要分割的整数 $ N $。
• 第 $ 2 $ 行给出各部分数字之和的上限 $ D $。

输出为以下格式，写入标准输出。

• 输出分割方式的数量对 $ 1,000,000,007 $ 取模的结果，占一行。

限制条件

• $ 1 \leq N \leq 10^{100} $
• $ 1 \leq D \leq 100,000 $

子任务

子任务 $ 1 $【$ 10 $ 分】

• 所有解都不超过 $ 1 $ 种。

子任务 $ 2 $【$ 30 $ 分】

• $ 1 \leq N \leq 10,000,000,000 $

子任务 $ 3 $【$ 60 $ 分】

• 无额外限制。

由 ChatGPT 4.1 翻译