We have a string SS consisting of decimal digits. A division of SS is created by dividing SS into contiguous substrings. For example, if SS is 0145217, two possible divisions are 014 5 21 7 and 0 14 52 17. Each digit must be used in exactly one substring, and each substring must be non-empty. If SS has LL digits, then there are exactly 2L−12L−1 possible divisions of it.

divisible divisions codejam solution

For Solution

Click Here!

We have a string SS consisting of decimal digits. A division of SS is created by dividing SS into contiguous substrings. For example, if SS is 0145217, two possible divisions are 014 5 21 7 and 0 14 52 17. Each digit must be used in exactly one substring, and each substring must be non-empty. If SS has LL digits, then there are exactly 2L12L−1 possible divisions of it.

Given a positive integer DD, a division of SS is called divisible by DD if for every pair of consecutive substrings, at least one of the integers they represent in base 1010 is divisible by DD. If D=7D=7, the first example division above is divisible because 01421, and 7 represent integers divisible by 77. The second example division is not divisible because 52 and 17 are consecutive substrings and neither represents an integer divisible by 77. Dividing 0145217 as 0145217 is divisible by any DD because there are no pairs of consecutive substrings.

Given SS and DD, count how many divisions of SS exist that are divisible by DD. Since the output can be a really big number, we only ask you to output the remainder of dividing the result by the prime 109+7109+7 (10000000071000000007).

Input

The first line of the input gives the number of test cases, TTTT lines follow. Each line represents a test case with a string of digits SS and a positive integer DD, as mentioned above.

Output

For each test case, output one line containing Case #xxyy, where xx is the test case number (starting from 1) and yy is the number of different divisions of SS that are divisible by DD, modulo the prime 109+7109+7 (10000000071000000007).

Limits

Time limit: 60 seconds.
Memory limit: 1 GB.
1T1001≤T≤100.
1D1061≤D≤106.

Test Set 1 (Visible Verdict)

11≤ the length of S1000S≤1000.

Test Set 2 (Hidden Verdict)

11≤ the length of S105S≤105.

Sample

Sample Input
content_copy
3
0145217 7
100100 10
5555 12
Sample Output
content_copy
Case #1: 16
Case #2: 30
Case #3: 1

In Sample Case #1, all 1616 divisible divisions of SS are:

  • 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, and
  • 014521 7.

 

In Sample Case #2, there are 25=3225=32 ways to divide in total. To get two consecutive substrings to not be divisible by 1010, we need both of them to not end in 00. The only 22 ways of doing that are 1 001 00 and 1 001 0 0, which means the other 3030 divisions of SS are divisible by 1010.

In Sample Case #3, no possible substring represents an even integer, which in turn means it is not divisible by 1212. Therefore, the only way to not have two consecutive substrings that are not divisible by 1212 is to not have two consecutive substrings at all, which can be done in only 11 way: 5555.

For Solution

Click Here!

Leave a Comment