Description

“夏天终于来了：是时候放松一下，享受乐趣，走到户外，感受美好天气了！”Alice 是一位非常敬业的护林员，在一个著名的国家公园工作。夏天，许多家庭会抽时间来这里露营、享受美好时光，而 Alice 的工作就是安排这些游客。

Alice 负责管理公园内的一个营地。该营地可以描述为一个 $N \times N$ 的矩阵，每个格子最多只能容纳一个帐篷。为了安排家庭入住营地，Alice 需要遵守以下规定：

• 只允许有 $1$、$2$ 或 $3$ 人的家庭入住营地。每个帐篷只能住一个家庭，且一个家庭不能分开住在多个帐篷里。
• 出于安全考虑，Alice 不希望某一行或某一列太拥挤或太空旷，因此每一行和每一列必须恰好有 $3$ 个人。
• 同时，根据公园的安全政策，每一行或每一列最多只能有 $2$ 个帐篷。

此外，Alice 已经提前知道，至少会有 $X$ 个三人家庭来营地，其余的空位将由足够多的一人或两人家庭填补。

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

$\begin{array}{llllll}1 & 2 & 0\\ 0 & 1 & 2\\ 2 & 0 & 1\end{array}$

$\begin{array}{llllll}3 & 0 & 0\\0 & 1 & 2\\0 & 2 & 1\end{array}$

以下是 $N=3$ 且 $X=1$ 时的不合法安排：

$\begin{array}{llllllll}1 & 2 & 0\\0 & 1 & 2\\ 2 & 0 & 1\end{array}$

$\begin{array}{llllllll}0 & 3 & 0\\3 & 0 & 0\\0 & 0 & 0\end{array}$

$\begin{array}{llllllll}1 & 2 & 0\\0 & 2 & 0\\2 & 0 & 1\end{array}$

$\begin{array}{llllllll}1 & 1 & 1\\1 & 1 & 1\\1 & 1 & 1 \end{array}$

• 第一个不合法，因为至少需要有一个三人家庭。
• 第二个不合法，因为第三行和第三列的人数不是 $3$。
• 第三个不合法，因为第二列人数超过了 $3$（而第二行人数不足 $3$）。
• 最后一个不合法，因为某一行或某一列有超过两个帐篷。

最后，Alice 想知道，在给定 $N$ 和 $X$ 的情况下，有多少种不同的安排方式。

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

Input Format

第一行输入一个整数 $T$，表示测试用例的数量。接下来有 $T$ 个测试用例。每个测试用例占一行，包含两个整数 $N$ 和 $X$，分别表示营地的行数（和列数）以及至少需要安排的三人家庭数量。

Output Format

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

答案可能很大，请输出对 $10^9+7$ 取模后的结果。

3
2 2
3 1
15 0

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

Hint

在第 1 个测试用例中，有两种不同的合法安排：

0 3  |  3 0
3 0  |  0 3

限制条件

• $1 \leq T \leq 200$。
• $0 \leq X \leq N$。

小数据集（6 分）

• 时间限制：5 秒。
• $1 \leq N \leq 20$。

大数据集（21 分）

• 时间限制：10 秒。
• $1 \leq N \leq 10^{6}$。

由 ChatGPT 4.1 翻译