题目描述

有一个和正整数 $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 的切分方案都满足条件。

更多样例

见附加文件。

数据范围

• 对于所有数据，$1\le T\le 100, 1\le n\le 10^5, 1\le D\le 10^6$。

  子任务编号	$n\le$	特殊限制	分值
  1	$1000$	-	$30$
  2	$10^5$	$\mathrm{gcd}(D,10)=1$	$20$
  3		$nD\le 10^6$
  4		-	$30$