题目描述

我们有一个由十进制数字组成的字符串 $\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

输入 #1

3
0145217 7
100100 10
5555 12

输出 #1

Case #1: 16
Case #2: 30
Case #3: 1

说明/提示

样例解释

在样例 #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 完成