P13406 [GCJ 2010 #3] Different Sum

我们为 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$ 取模的结果。

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

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

**样例解释** 以下是和为 $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 翻译