“夏天终于到了：是时候放松一下，找点乐子，去户外享受美好的天气了！”Alice 说道。她是一位非常敬业的护林员，在一家受欢迎的国家公园工作。夏天期间，许多家庭会抽出时间来这里露营，度过愉快的时光，而接待游客正是 Alice 的工作。

Alice 负责公园内众多营地中的一个。营地可以描述为一个 $N \times N$ 的矩阵，其中每个单元格最多只能容纳一个帐篷。为了安排营地中的家庭，Alice 需要遵守以下几项规定：

• 营地只允许 1、2 或 3 人的家庭入住。此外，每个帐篷只能容纳一个家庭的成员，且家庭成员不能分散在多个帐篷中。
• 出于安全考虑，Alice 不希望行或列过于拥挤或过于空旷，因此她要求每行和每列恰好有 3 名成员。
• 此外，根据公园的安全政策，任何行或列中的帐篷数量不得超过 2 个。

此外，Alice 事先知道至少会有 $X$ 个三口之家来访，并且会有足够的一口之家或两口之家来填满营地的其余部分。

例如，以下是 $N = 3$ 且 $X = 0$ 时的有效安排：

1  2  0  |  3  0  0
0  1  2  |  0  1  2
2  0  1  |  0  2  1

以下是 $N = 3$ 且 $X = 1$ 时的无效安排：

1  2  0  |  0  3  0  |  1  2  0  |  1  1  1
0  1  2  |  3  0  0  |  0  2  0  |  1  1  1
2  0  1  |  0  0  0  |  2  0  1  |  1  1  1

• 第一个安排无效，因为应该至少有一个三口之家。
• 第二个例子无效，因为第三行（和第三列）的人数不是 3。
• 第三个例子无效，因为第二列的人数超过了 3（且第二行的人数少于 3）。
• 最后一个例子中，每行或每列的帐篷数量超过了 2 个。

最后，Alice 喜欢让事情变得有趣。她想知道在给定 $N$ 和 $X$ 的情况下，有多少种不同的安排方式。

如果两个安排 A 和 B 中，某个单元格在一个安排中有帐篷而另一个没有，或者两个安排中同一单元格都有帐篷但人数不同，则认为这两个安排是不同的。

输入格式

输入的第一行包含 $T$，即测试用例的数量。接下来是 $T$ 个测试用例。每个测试用例由一行组成，包含两个整数 $N$ 和 $X$，分别对应 Alice 营地的行数（和列数）以及最少需要的三口之家的数量。

输出格式

对于每个测试用例，输出一行 "Case #X: Y"，其中 X 是测试用例编号（从 1 开始），Y 是可能的安排数量。

答案可能非常大，请将答案对 $10^9 + 7$ 取模。

数据范围

$1 \le T \le 200$。

$0 \le X \le N$。

小数据范围

$1 \le N \le 20$。

大数据范围

$1 \le N \le 10^6$。

样例

样例输入 1

3
2 2
3 1
15 0

样例输出 1

Case #1: 2
Case #2: 24
Case #3: 738721209

说明

在案例 #1 中，有两种不同的有效安排：

0 3  |  3 0
3 0  |  0 3