题目描述

为了庆祝 Googleland 的周年纪念，$N$ 对夫妇将乘坐一条划艇出游。这条划艇很长，但宽度只够一人，因此人们会从前到后坐成一排。

然而，在一次试航中，船并没有移动！经过调查，主办方发现有些新婚夫妇并没有在划船，而是一直在给对方写情诗。具体来说，有 $M$ 对新婚夫妇。如果一对新婚夫妇的两人相邻而坐，他们会忙于写诗而不会划船。

现在主办方找到了你——Googleland 最聪明的人，问你：有多少种可能的方式将这 $2N$ 个人安排在划艇上，使得对于每对新婚夫妇，两人的座位都不相邻？如果两种安排在船上的某个位置坐的人不同，则视为不同的方式。注意，在计数时，一对夫妇中的两个人不被视为可互换的。由于答案可能非常大，主办方只想知道结果对 $1000000007\ (10^9+7)$ 取模的值。

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例由一行两个整数 $N$ 和 $M$ 组成，含义如上所述。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是可能的安排数对 $1000000007\ (10^9+7)$ 取模的结果。

5
2 1
2 2
3 1
3 2
10 5

Case #1: 12
Case #2: 8
Case #3: 480
Case #4: 336
Case #5: 560963525

提示

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是可能的安排数对 $1000000007\ (10^9+7)$ 取模的结果。

ABab ABba AbaB AbBa
aBAb aBbA abAB abBA
BAba BabA bABa baBA

在样例 #2 中，两对夫妇都是新婚夫妇，因此 A 和 a 不能相邻，B 和 b 也不能相邻。它们可以排列成以下 $8$ 种方式：

ABab AbaB aBAb abAB
BAba BabA bABa baBA

限制条件

$1 \le T \le 100$。

小数据集（测试集 1 – 可见）

$1 \le M \le N \le 100$。

大数据集（测试集 2 – 隐藏）

$1 \le M \le N \le 100000$。

翻译由 DeepSeek V4 Pro 完成