P13406 [GCJ 2010 #3] Different Sum

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 $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$. 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$.

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$.

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$.

**Sample 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=(20)_4$: ``` 20 11 13 10 -- 3 1 3 20 -- -- 1 20 20 -- 20 ``` **Limits** - $1 \leq T \leq 20$. **Small dataset (7 Pts, Test set 1 - Visible)** - Time limit: ~~30~~ 3 seconds. - $1 \leq N \leq 100$. - $2 \leq B \leq 10$. **Large dataset (22 Pts, Test set 2 - Hidden)** - Time limit: ~~120~~ 20 seconds. - $1 \leq N \leq 10^{18}$. - $2 \leq B \leq 70$.