P13234 [GCJ 2015 Finals] Campinatorics

“夏天终于来了：是时候放松一下，享受乐趣，走到户外，感受美好天气了！”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$ 满足：存在某个格子在一个安排中有帐篷而另一个没有，或者同一个格子都有帐篷但帐篷内人数不同，则认为这两个安排是不同的。

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

对于每个测试用例，输出一行，格式为 "Case #X: Y"，其中 $X$ 是测试用例编号（从 1 开始），$Y$ 是可能的安排数量。 答案可能很大，请输出对 $10^9+7$ 取模后的结果。

在第 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 翻译