Apricot Rules LLC 正在开发一种新的简化网络协议，并希望展示他们的路由算法。在他们的设计中，网络由编号为 $1$ 到 $M$ 的 $M$ 台机器组成，每对机器之间都由一条直接链路连接。每条链路都被赋予一个 $1$ 到 $M \times (M - 1)/2$ 之间的唯一整数优先级，每台机器都根据这些优先级来路由流量。

不幸的是，该路由算法过于激进，会将来自某台机器的所有流量都通过连接到该机器的最高优先级链路进行路由。这可能会导致某些机器组与其他机器隔离开来。

形式上，我们称机器 $m$ 使用链路 $\ell$ 当且仅当 $\ell$ 是连接到 $m$ 的最高优先级链路。我们还称一条链路是“活跃的”，如果它被其连接的两台机器中的至少一台所使用。给定链路优先级，原始网络会被划分为若干个不相交的内联网（intranets）。两台机器属于同一个内联网，当且仅当它们之间存在一条仅使用活跃链路的路径。

例如，如上图左侧所示，只有优先级为 $6$ 和 $5$ 的链路是活跃的。这创建了两个不相交的内联网。然而，在右侧的示例中，有三条链路是活跃的，这导致所有 $4$ 台机器组成了一个内联网。

作为 Apricot Rules LLC 质量保证团队的一员，你正在调查该问题的严重程度。如果优先级是在所有 $(M \times (M - 1)/2)!$ 种可能的分配方式中均匀随机选取的，你对恰好存在 $K$ 个内联网的概率感兴趣。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例由一行组成，包含两个整数 $M$ 和 $K$：分别表示机器的数量和目标内联网的数量。

输出格式

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是所求概率对质数 $10^9 + 7$ ($1000000007$) 取模的结果。该概率定义如下：将概率表示为不可约分数 $p/q$（其中 $p$ 和 $q$ 为非负整数且使 $p+q$ 最小化）。则 $y$ 必须等于 $p \cdot q^{-1} \pmod{10^9 + 7}$，其中 $q^{-1}$ 是 $q$ 关于模 $10^9 + 7$ 的模逆元。可以证明，在该问题的约束条件下，这样的数总是存在且唯一的。

数据范围

内存限制：1 GB。 $1 \le T \le 50$。 $1 \le K \le M/2$。

子任务 1

时间限制：20 秒。 $2 \le M \le 50$。

子任务 2

时间限制：60 秒。 $2 \le M \le 5 \times 10^5$。

样例

样例输入 1

3
5 2
5 1
6 3

样例输出 1

Case #1: 428571432
Case #2: 571428576
Case #3: 47619048

说明

在样例 #1 中，考虑以下情况。设 $M = 5$ 台机器为 $1, 2, 3, 4, 5$，并将连接机器 $a$ 和机器 $b$ 的链路记为 $(a, b)$。假设链路 $(1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5)$ 的优先级分别为 $9, 8, 7, 6, 5, 4, 3, 2, 1, 10$。那么机器 $1$ 和 $2$ 使用链路 $(1, 2)$，机器 $3$ 使用链路 $(1, 3)$，机器 $4$ 和 $5$ 使用链路 $(4, 5)$。因此，三条链路 $(1, 2), (1, 3), (4, 5)$ 是活跃的，存在两个内联网 $\{1, 2, 3\}$ 和 $\{4, 5\}$。由于 $K = 2$，这种情况计入答案。

我们可以发现，在 $10! = 3628800$ 种分配方式中，有 $1555200$ 种方式恰好产生 $2$ 个内联网，因此概率为 $3/7$。

在样例 #2 中，概率为 $4/7$。

在样例 #3 中，概率为 $1/21$。