【思路要点】

• 将划分和标号放在一起考虑，即依次放入标号为 $1\sim{}\frac{N\times M}{3}$1∼3N×M​ 的骨牌，保证当前放入区域的轮廓线为单调的，不难发现放置方案与题目中所要计算的方案数一一对应。
• 将轮廓线描述为 $N$N 个 “上” 和 $M$M 个 “右” ，用 $1$1 来表示 “上” ， $0$0 来表示 “右” ，则初始时的轮廓线为 $111\dots1000\dots0$111…1000…0 。
• 观察转移，也即放置一个新的骨牌的方式：
  $1000\rightarrow 0001\\1010\rightarrow 0011\\1100\rightarrow 0101\\1110\rightarrow 0111$1000→00011010→00111100→01011110→0111
• 可以发现，所有的转移可以归纳为 “使得一个 $1$1 与 $3$3 格外的一个 $0$0 交换位置，且中间的数对转移没有影响” 。
• 将模 $3$3 相同的位置分别考虑，最后用组合数合并答案，则转移即为 $10\rightarrow01$10→01 。
• 设初始时共有 $x$x 个 $1$1 ， $y$y 个 $0$0 ，则所有转移方式与对 $x\times y$x×y 的网格图，每个点向上方和左方的一个点连有向边的网格图拓扑排序的方案一一对应。
• 可以用杨氏矩阵理论中的钩子公式来计算该图的拓扑排序数。
• 时间复杂度 $O(N\times M+T\times(N+M)Log(N+M))$O(N×M+T×(N+M)Log(N+M)) 。

【代码】

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e4 + 5;
const int MAXS = 4e7 + 5;
const int P = 1e9 + 7;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
template <typename T> void write(T x) {
	if (x < 0) x = -x, putchar('-');
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
template <typename T> void writeln(T x) {
	write(x);
	puts("");
}
int fac[MAXS], inv[MAXN], num[MAXN], cnt[3][2];
int power(int x, int y) {
	if (y == 0) return 1;
	int tmp = power(x, y / 2);
	if (y % 2 == 0) return 1ll * tmp * tmp % P;
	else return 1ll * tmp * tmp % P * x % P;
}
void init() {
	fac[0] = 1;
	for (int i = 1; i < MAXS; i++)
		fac[i] = 1ll * fac[i - 1] * i % P;
	for (int i = 1; i < MAXN; i++)
		inv[i] = power(i, P - 2);
}
void update(int &x, int y) {
	x += y;
	if (x >= P) x -= P;
}
int work(int n, int m) {
	int ans = 1;
	for (int i = 2; i <= n + m; i++) {
		int l = max(1, i - m), r = min(n, i - 1);
		ans = 1ll * ans * power(inv[i - 1], r - l + 1) % P;
	}
	return ans;
}
int main() {
	freopen("trominoes.in", "r", stdin);
	freopen("trominoes.out", "w", stdout);
	init();
	int T; read(T);
	while (T--) {
		int n, m; read(n), read(m);
		for (int i = 1; i <= n; i++)
			num[i] = 1;
		for (int i = 1; i <= m; i++)
			num[i + n] = 0;
		memset(cnt, 0, sizeof(cnt));
		for (int i = 1; i <= n + m; i++)
			cnt[i % 3][num[i]]++;
		int ans = fac[cnt[1][0] * cnt[1][1] + cnt[2][0] * cnt[2][1] + cnt[0][0] * cnt[0][1]];
		ans = 1ll * ans * work(cnt[1][1], cnt[1][0]) % P;
		ans = 1ll * ans * work(cnt[2][1], cnt[2][0]) % P;
		ans = 1ll * ans * work(cnt[0][1], cnt[0][0]) % P;
		writeln(ans);
	}
	return 0;
}