나누어떨어지는 분할

십진 숫자로 이루어진 문자열 $\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}$이 주어질 때, 모든 연속한 두 부분 문자열의 쌍에 대해 이들이 $10$진법으로 나타내는 정수 중 적어도 하나가 $\mathbf{D}$로 나누어떨어지면 $\mathbf{S}$의 분할을 $\mathbf{D}$로 나누어떨어진다고 한다. $\mathbf{D}=7$이면, 위의 첫 번째 예시 분할은 014, 21, 7이 $7$로 나누어떨어지는 정수를 나타내므로 나누어떨어진다. 두 번째 예시 분할은 52과 17이 연속한 부분 문자열이고 어느 쪽도 $7$로 나누어떨어지는 정수를 나타내지 않으므로 나누어떨어지지 않는다. 0145217을 0145217로 분할하면 연속한 부분 문자열의 쌍이 없으므로 어떤 $\mathbf{D}$에 대해서도 나누어떨어진다.

$\mathbf{S}$과 $\mathbf{D}$이 주어질 때, $\mathbf{D}$로 나누어떨어지는 $\mathbf{S}$의 분할이 몇 개인지 센다. 출력값은 매우 큰 수일 수 있으므로, 결과를 소수 $10^9+7$ ($1000000007$)로 나눈 나머지만 출력한다.

제한

시간 제한: 60초. 메모리 제한: 1 GB. $1 \le \mathbf{T} \le 100$. $1 \le \mathbf{D} \le 10^6$.

테스트 세트 1 (결과 공개)

$1 \le$은 $\mathbf{S} \le 1000$의 길이이다.

테스트 세트 2 (결과 비공개)

$1 \le$은 $\mathbf{S} \le 10^5$의 길이이다.

입력의 첫 번째 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 줄이 주어진다. 각 줄은 위에서 설명한 숫자 문자열 $\mathbf{S}$과 양의 정수 $\mathbf{D}$로 이루어진 하나의 테스트 케이스를 나타낸다.

각 테스트 케이스마다 Case #$x$: $y$을 포함하는 한 줄을 출력한다. 여기서 $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$은 $\mathbf{D}$로 나누어떨어지는 $\mathbf{S}$의 서로 다른 분할의 수를 소수 $10^9+7$ ($1000000007$)로 나눈 나머지이다.

예제 케이스 #1에서, $\mathbf{S}$의 나누어떨어지는 분할 $16$개는 모두 다음과 같다.

• 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$로 끝나지 않아야 한다. 그렇게 하는 유일한 $2$가지 방법은 1 001 00와 1 001 0 0이므로, $\mathbf{S}$의 나머지 $30$개 분할은 $10$로 나누어떨어진다.

예제 케이스 #3에서, 가능한 어떤 부분 문자열도 짝수를 나타내지 않으며, 따라서 $12$로 나누어떨어지지 않는다. 그러므로 $12$로 나누어떨어지지 않는 연속한 두 부분 문자열이 존재하지 않게 하는 유일한 방법은 연속한 두 부분 문자열 자체가 없게 하는 것이며, 이는 단 하나의 방법인 $1$가지로만 가능하다: 5555.