Counting Cryptarithm Equations

Problem

A cryptarithm equation is an addition equation written so that every summand and the sum are aligned to the same right border, like this:

On top of that, for every column all digits of the summands in that column must be different. The sum is not part of this condition. In the equation above the first column holds only the digit 1, the second column holds 2, 3 and 2, and the third column holds 4, 1 and 5. This equation is not a cryptarithm equation, because the second column holds two 2's. Replacing the last summand with 15, and the sum with 170, turns it into one.

A summand is always positive and is written without leading zeros. A summand shorter than the longest one puts no digit at all in the columns it does not reach. The order of the summands does not matter, so two equations that differ only in the order of the summands count as the same equation.

Bases other than 10 are allowed. A digit in base $B$ is an integer between $0$ and $B-1$ . Here is a cryptarithm equation in base 23:

 I7B
 JJJ
----
1F47

Here "I" is the digit 18, "B" is 11, "J" is 19 and "F" is 15. Written in base 10, the two summands are $18 \times 23^2 + 7 \times 23 + 11 = 9694$ and $19 \times 23^2 + 19 \times 23 + 19 = 10507$ , and the sum is $1 \times 23^3 + 15 \times 23^2 + 4 \times 23 + 7 = 20201$ . Letters are used for digits of 10 and more only to keep the example readable. How such a digit is written on paper does not matter in this problem.

Count the cryptarithm equations whose sum is $N$ in base $B$ . The answer can be very large, so print it modulo $1000000007$ .

Input

The first line has the number of test cases $T$ . Each of the next $T$ lines has two positive integers $N$ and $B$ . Every number in the input is written in base 10.

Limits

$1 \le T \le 20$
$1 \le N \le 10^{18}$
$2 \le B \le 70$

Output

For each test case, print one line of the form Case #x: y. Here x is the test case number starting from 1, and y is the number of cryptarithm equations whose sum is the given $N$ in base $B$ , taken modulo $1000000007$ . Print y in base 10.

Hint

In base 10 there are four cryptarithm equations with sum 6: $6 = 6$ , $1 + 5 = 6$ , $2 + 4 = 6$ and $1 + 2 + 3 = 6$ .

In base 4 there are also four equations with sum $8 = 20_4$ :

20
--
20