Description

我们为 Google Code Jam 2010 设计了一个很棒的问题，涉及选手们解决一个“字谜算式”（cryptarithm）。但我们需要你帮助生成该问题的测试用例；更准确地说，我们关心的是那些足够“好”（具体定义见下文）以便转换为字谜算式的加法等式。

你不需要了解什么是字谜算式来解决本题，因为我们会提供所有必要的定义。我们将字谜算式定义为如下格式的加法等式：所有被加数（加数）和结果（和）都右对齐，如下所示：

124
 31
 25
---
180

此外，对于字谜算式的每一列，所有加数在该列上的数字都必须互不相同。注意，这个约束不包括结果（和）。例如，上述等式的第一列只有数字 $1$，第二列有数字 $2,3$ 和 $2$，第三列有数字 $4, 1$ 和 $5$。这个等式不是一个字谜算式，因为第二列出现了两个 $2$。但如果我们将最后一个加数替换为 $15$（和替换为 $170$），那么它就是一个字谜算式。

注意，字谜算式中的加数都为正数，且不允许有前导零。加数的顺序不重要（换句话说，仅加数顺序不同的两个等式被视为相同的等式）。

上面的例子是在 $10$ 进制下的，但我们也对其他进制下的字谜算式感兴趣。注意，在 $b$ 进制下，“数字”可以是 $0$ 到 $b-1$ 之间的任意整数。下面是一个 $23$ 进制下的字谜算式：

 I7B
 JJJ
----
1F47

在这个例子中，"I" 代表数字 $18$，"B" 代表数字 $11$，"J" 代表数字 $19$，"F" 代表数字 $15$。用十进制表示，这两个加数分别为 $18\times 23^2 + 7\times 23 + 11 = 9694$ 和 $19\times 23^2 + 19\times 23 + 19 = 10507$，和为 $1\times 23^3 + 15\times 23^2 + 4\times 23 + 7 = 20201$。请注意，用字母表示 $10$ 及以上的数字只是为了例子更清晰；在本题中如何表示这些数字并不重要。

给定和 $N$ 以及进制 $B$，有多少个不同的字谜算式？

由于答案可能非常大，请输出对 $1000000007$ 取模的结果。

Input Format

输入的第一行是测试用例数 $T$。接下来的 $T$ 行，每行包含两个正整数 $N$ 和 $B$。所有输入数字均为十进制。

Output Format

对于每个测试用例，输出一行，格式为 "Case #$x$: $y$"，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是满足条件的字谜算式数量。由于答案可能很大，请输出对 $1000000007$ 取模的结果。输出本身应为十进制。

2
6 10
8 4

Case #1: 4
Case #2: 4

Hint

样例解释

以下是和为 $6$ 的 $4$ 个字谜算式：

6   1   2   1
-   5   4   2
6   -   -   3
    6   6   -
            6

以下是在 $4$ 进制下和为 $8=(20)_4$ 的 $4$ 个字谜算式：

20   11   13   10
--    3    1    3
20   --   --    1
     20   20   --
               20

数据范围

• $1 \leq T \leq 20$。

小数据范围（7 分，测试点 1 - 可见）

• 时间限制：30 3 秒。
• $1 \leq N \leq 100$。
• $2 \leq B \leq 10$。

大数据范围（22 分，测试点 2 - 隐藏）

• 时间限制：120 20 秒。
• $1 \leq N \leq 10^{18}$。
• $2 \leq B \leq 70$。

由 ChatGPT 4.1 翻译