501000050 - 数位

有一个和正整数 D 和一个长为 n 的，由 0 到 9 构成的字符串 S。

字符串中连续的一段被称为这个字符串的子串。如果一个字符串视为十进制数（可以有前导 0）时是 D 的倍数，就称它是一个倍数串。

现在要把这个长为 n 的字符串切成若干段，也就是若干个首尾相连的子串。要求，切分后任意一对相邻的子串中至少有一个子串是倍数串；切分后的总段数小于 2 也可以。

问有多少种切分方案满足条件，答案对 10^9+7 取模。

输入格式

输入文件名为 digit.in。

第一行一个正整数 T 表示数据组数。

接下来 T 行，每行一个字符串 S 和一个正整数 D 表示一组数据。

输出格式

输出文件名为 digit.out。

共 T 行，依次表示每组数据的答案。对 10^9+7 取模。

样例

样例输入 1

3
0145217 7
100100 10
5555 12

样例输出 1

16
30
1

样例解释 1

第一组数据的合法切分方案：

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

第二组数据除了 1 001 00 和 1 001 0 0 的切分方案都满足条件。