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 翻译