Sums with Distinct Column Digits

A cryptarithm equation is an addition written with every summand and the sum aligned to the same right border, like this.

124
 31
 25
---
180

The summands are positive integers written without leading zeros. In every column, the digits of the summands standing in that column must be pairwise different. The digits of the sum are not part of this condition. The first column above holds only 1, the second column holds 2, 3 and 2, and the third column holds 4, 1 and 5. The second column holds 2 twice, so this is not a cryptarithm equation. Replacing the last summand with 15 and the sum with 170 turns it into one.

The order of the summands does not matter. Two equations that differ only in the order of the summands count as the same equation.

Bases other than 10 are allowed. In base $b$, a single digit is any integer from 0 to $b-1$. Here is a cryptarithm equation in base 23.

 I7B
 JJJ
----
1F47

I stands for the digit 18, B for 11, J for 19, and F for 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 for digits of 10 and above are only a notation that keeps this example readable, and how such digits are written has nothing to do with the problem.

How many cryptarithm equations in base $B$ have sum $N$? The count can be very large, so report it modulo $1000000007$.

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 100$
• $2 \le B \le 10$

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

Four cryptarithm equations in base 10 have sum 6.

6
-
6

1
5
-
6

2
4
-
6

1
2
3
-
6

Four cryptarithm equations in base 4 have sum $20_4 = 8$.

20
--
20

11
 3
--
20

13
 1
--
20

10
 3
 1
--
20