P13046 [GCJ 2021 Finals] Divisible Divisions

我们有一个由十进制数字组成的字符串 $\mathbf{S}$。$\mathbf{S}$ 的一个**分割**是通过将 $\mathbf{S}$ 划分为连续的若干子串得到的。例如，若 $\mathbf{S}$ 为 `0145217`，则两种可能的分割为 `014 5 21 7` 和 `0 14 52 17`。每个数字必须恰好出现在一个子串中，且每个子串必须非空。如果 $\mathbf{S}$ 有 $L$ 个数字，则它共有 $2^{L-1}$ 种可能的分割方式。 给定一个正整数 $\mathbf{D}$，若 $\mathbf{S}$ 的某个分割满足：对于任意两个相邻的子串，它们表示的十进制整数中至少有一个能被 $\mathbf{D}$ 整除，则称该分割是**可被 $\mathbf{D}$ 整除的**。若 $\mathbf{D}=7$，上述第一个示例分割是可被整除的，因为 `014`、`21` 和 `7` 表示的整数均能被 7 整除。第二个示例分割不可被整除，因为 `52` 和 `17` 是相邻子串且均不能被 7 整除。将 `0145217` 分割为 `0145217`（即不分割）对任意 $\mathbf{D}$ 都是可被整除的，因为此时不存在相邻子串对。 给定 $\mathbf{S}$ 和 $\mathbf{D}$，统计 $\mathbf{S}$ 的可被 $\mathbf{D}$ 整除的分割数量。由于结果可能非常大，只需输出其对质数 $10^{9}+7$（即 $1000000007$）取模后的余数。

输入的第一行包含测试用例的数量 $\mathbf{T}$。随后 $\mathbf{T}$ 行，每行表示一个测试用例，包含一个数字字符串 $\mathbf{S}$ 和一个正整数 $\mathbf{D}$，如上所述。

对于每个测试用例，输出一行 `Case #x: y`，其中 $x$ 为测试用例编号（从 1 开始），$y$ 为 $\mathbf{S}$ 的可被 $\mathbf{D}$ 整除的分割数量，对 $10^{9}+7$ 取模后的结果。

**样例解释** 在样例 #1 中，$\mathbf{S}$ 的所有 16 种可被 7 整除的分割为： - 0145217, - 0 145217, - 0 14 5217, - 0 14 5 217, - 0 14 5 21 7, - 0 14 521 7, - 0 145 217, - 0 145 21 7, - 0 14521 7, - 014 5217, - 014 5 217, - 014 5 21 7, - 014 521 7, - 0145 217, - 0145 21 7, 和 - 014521 7. 在样例 #2 中，共有 $2^{5}=32$ 种分割方式。若要使两个相邻子串均不被 10 整除，则这两个子串的末尾均不能为 0。唯一满足此条件的分割是 `1 001 00` 和 `1 001 0 0`，因此其余 30 种分割均是可被 10 整除的。 在样例 #3 中，没有任何子串表示的整数是偶数（即无法被 12 整除）。因此，唯一避免两个相邻子串均不被 12 整除的方式是不进行任何分割，即仅有一种分割：`5555`。 **数据范围** - $1 \leq \mathbf{T} \leq 100$。 - $1 \leq \mathbf{D} \leq 10^{6}$。 **测试集 1（10 分，可见判定）** - $1 \leq \mathbf{S}$ 的长度 $\leq 1000$。 **测试集 2（35 分，隐藏判定）** - $1 \leq \mathbf{S}$ 的长度 $\leq 10^{5}$。 翻译由 DeepSeek V3 完成