Problem
We have come up with a wonderful problem for Google Code Jam 2010 that involves contestants solving a cryptarithm. But we need your help in creating testcases for the problem; more precisely, we're concerned with addition equations that are good enough (in the sense defined below) for conversion into cryptarithms.
You don't need to know what a cryptarithm is to solve this problem, as we'll provide all required definitions. We define a cryptarithm equation to be an addition equation written in such a way that all summands (numbers being added) and the sum are aligned to the same right border like this:
124 31 25 --- 180
Additionally, for each column of a cryptarithm equation, all digits of the summands in that column must be different. Note that we don't include the sum in this constraint. So for example in the above equation the first column contains only digit 1, the second column contains digits 2,3 and 2, and the third column contains digits 4, 1 and 5. This equation is not a cryptarithm equation since the second column contains two 2's. However, it would be a cryptarithm equation if we replaced the last summand with 15 (and the sum with 170). Note that summands in a cryptarithm equation are always positive and written without leading zeros. The order of summands is not important (in other words, two equations which differ only in the order of the summands are considered the same). The example above was in base 10, but we're also interested in cryptarithm equations in other bases. Note that a "digit" in base b could mean any integer between 0 and b-1. Here is a cryptarithm equation in base 23:
I7B JJJ ---- 1F47
In this example, "I" stands for digit 18, "B" stands for digit 11, "J" stands for digit 19, and "F" stands for digit 15. In decimal notation, the two summands are 18232 + 723 + 11 = 9694 and 19232 + 1923 + 19 = 10507, and the sum is 1233 + 15232 + 4*23 + 7 = 20201. Please note that denoting digits of 10 and more with letters was done purely for the clarity of the example; it doesn't really matter in this problem how exactly we denote such digits in writing. How many cryptarithm equations are there with the given sum N in the given base B? Since the answer might be very large, please output it modulo 1000000007.
Input
The first line of the input gives the number of test cases, T. T lines follow. Each contains two positive integers N and B. All input numbers are given in base 10.
Output
For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is the number of different cryptarithm equations with the given sum. Since this number can be very big, please output it modulo 1000000007. Of course, the output itself should be in base 10.
Limits
Memory limit: 1GB.
1 ≤ T ≤ 20.
Small dataset (Test set 1 - Visible; 7 Points)
Time limit: 30 5 seconds.
1 ≤ N ≤ 100.
2 ≤ B ≤ 10.
Large dataset (Test set 2 - Hidden; 22 Points)
Time limit: 120 30 seconds.
1 ≤ N ≤ 1018.
2 ≤ B ≤ 70.
Sample
2 6 10 8 4
Case #1: 4 Case #2: 4
Explanation
Here are the 4 cryptarithm equations with sum 6:
6 1 2 1 - 5 4 2 6 - - 3 6 6 - 6
And here are the 4 cryptarithm equations in base 4 with sum 8=204:
20 11 13 10 -- 3 1 3 20 -- -- 1 20 20 -- 20