我们为 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$ 取模的结果。当然，输出本身应以十进制表示。

数据范围

$1 \le T \le 20$。

小数据（测试集 1 - 可见；7 分）

$1 \le N \le 100$。

$2 \le B \le 10$。

大数据（测试集 2 - 隐藏；22 分）

$1 \le N \le 10^{18}$。

$2 \le B \le 70$。

样例

样例输入 1

2
6 10
8 4

样例输出 1

Case #1: 4
Case #2: 4

说明

以下是总和为 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