P16661 [GKS 2018 #H] Let Me Count The Ways

为了庆祝 Googleland 的周年纪念，$N$ 对夫妇将乘坐一条划艇出游。这条划艇很长，但宽度只够一人，因此人们会从前到后坐成一排。 然而，在一次试航中，船并没有移动！经过调查，主办方发现有些新婚夫妇并没有在划船，而是一直在给对方写情诗。具体来说，有 $M$ 对新婚夫妇。如果一对新婚夫妇的两人相邻而坐，他们会忙于写诗而不会划船。 现在主办方找到了你——Googleland 最聪明的人，问你：有多少种可能的方式将这 $2N$ 个人安排在划艇上，使得对于每对新婚夫妇，两人的座位都不相邻？如果两种安排在船上的某个位置坐的人不同，则视为不同的方式。注意，在计数时，一对夫妇中的两个人不被视为可互换的。由于答案可能非常大，主办方只想知道结果对 $1000000007\ (10^9+7)$ 取模的值。

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

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

对于每个测试用例，输出一行，格式为 `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 完成