2555. [CCPC2015][HDU5548] 麻将 Mahjong

【题目描述】

麻将源于中国，流行于世界。这道题不要求你会打麻将，而且我们将使用不同的规则。

在我们的麻将中，玩家有 $4K$ 张牌。每张牌上写着一个点数，$1\sim K$ 的每个点数都有四张完全相同的牌。例如，对于 $K=5$，牌组就是：$1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5$.

玩家的目标是从牌组中选出 $M$ 张，形成一副和牌。一幅和牌由若干（可能为零）个三元组和恰好一个对子组成。一个对子包含两张点数相同的牌。一个三元组要么是三张点数相等的牌（如 $222$），要么是三张点数连续的牌（例如，$345$）。不考虑点数循环的情况，例如，$451$ 不是合法的三元组。

给定 $K$ 和 $M$，求能够组成多少种不同的和牌方案。两种方案相同当且仅当它们包含的牌的集合相同，无论它们的三元组和对子为何。我们认为相同点数的牌完全相同。例如，对于 $K=4,M=8$，如下两种和牌相同：

$1 2 3, 1 2 3, 4 4$

$1 1, 2 3 4, 2 3 4$

【输入格式】

第一行一个正整数 $T(1\le T\le 100)$，代表数据组数。

接下来 $T$ 行，每行两个正整数 $K(1\le K\le 200),M(2\le M\le \min\{200,4K\},M\equiv 2\pmod{3})$.

【输出格式】

对每组数据，输出一行形如 $\mathrm{Case\ \#x:\ y}$，其中 $x$ 是第几组数据，从 $1$ 编号，$y$ 是和牌方案数模 $10^9+7$ 的值。

【输入样例】

4
1 2
3 5
4 5
9 14

【输出样例】

Case #1: 1
Case #2: 9
Case #3: 20
Case #4: 13259

【样例解释】

对第一组数据，只有四张牌：$1,1,1,1$，因此唯一和牌方案为 $1 1$。

(注意所有的 $1$ 完全相同，所以不考虑你选取哪两张。)

对第二组数据，有 $12$ 张牌：$ 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3 $，和牌方案包含一个三元组和一个对子。九种方案如下:

$1 1 1, 2 2$
$1 1 1, 3 3$
$2 2 2, 1 1$
$2 2 2, 3 3$
$3 3 3, 1 1$
$3 3 3, 2 2$
$1 2 3, 1 1$
$1 2 3, 2 2$
$1 2 3, 3 3$

注意 $3 3, 1 1 1$ 和 $1 1 1, 3 3$ 相同，因为它们包含的牌的集合相同。

【题目来源】

The 2015 China Collegiate Programming Contest