发现去掉匹配的 \(2k\) 个括号后，剩下的串一定形如 \()) \ldots )(( \ldots (\)，其中右括号数量为 \(a = m - k\)，左括号数量为 \(b = n - k\)。
考虑把剩下的串像 \()) \ldots ) \mid (( \ldots (\) 一样分成两半。枚举左半边加入了 \(\frac{i}{2}\) 对匹配，则长度为 \(a + i\)，右半边长度为 \(b + 2k - i\)。根据乘法原理把两半的方案数相乘即可。下面只讨论左半边的计算，右半边类似。
考虑折线图。相当于每一步可以向右上或右下走，求 \((0, 0) \to (a + i, -a)\) 且不接触直线 \(y = -a - 1\) 的方案数。这是经典问题。考虑容斥，总方案数 \(\binom{a + i}{a + \frac{i}{2}}\) 减去接触的方案数。把折线与 \(y = -a - 1\) 最后一个交点之前的部分对称过去，相当于 \((0, -2a - 2) \to (a + i, -a)\)。可以解得需要向右上走 \(a + \frac{i}{2} + 1\) 步，所以接触的方案数就是 \(\binom{a + i}{a + \frac{i}{2} + 1}\)。
注意为了避免算重，我们钦定左半边到达 \((a + i, -a)\) 是最后一次接触直线 \(y = -a\)。也就是说右半边除了第一步外不能接触直线 \(y = -a\)。钦定第一步向右上走后也可以类似地计算。
时间复杂度 \(O(\sum k)\)。
code
// Problem: D. Balanced Subsequences
// Contest: Codeforces - Codeforces Round 921 (Div. 1)
// URL: https://codeforces.com/contest/1924/problem/D
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 4020;
const int N = 4000;
const ll mod = 1000000007;
inline ll qpow(ll b, ll p) {
ll res = 1;
while (p) {
if (p & 1) {
res = res * b % mod;
}
b = b * b % mod;
p >>= 1;
}
return res;
}
ll n, m, K, fac[maxn], ifac[maxn];
inline void init() {
fac[0] = 1;
for (int i = 1; i <= N; ++i) {
fac[i] = fac[i - 1] * i % mod;
}
ifac[N] = qpow(fac[N], mod - 2);
for (int i = N - 1; ~i; --i) {
ifac[i] = ifac[i + 1] * (i + 1) % mod;
}
}
inline ll C(ll n, ll m) {
if (n < m || n < 0 || m < 0) {
return 0;
} else {
return fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}
}
void solve() {
scanf("%lld%lld%lld", &n, &m, &K);
if (K > n || K > m) {
puts("0");
return;
}
ll a = m - K, b = n - K, ans = 0;
for (int i = 0; i <= K * 2; i += 2) {
ll la = a + i, lb = b + K * 2 - i;
ll x = (C(la, i / 2) - C(la, i / 2 - 1) + mod) % mod;
if (b + K - i / 2 == 0) {
ans = (ans + x) % mod;
continue;
}
if (b == 0) {
continue;
}
ll y = (C(lb - 1, K - i / 2) - C(lb - 1, K - i / 2 - 1) + mod) % mod;
ans = (ans + x * y) % mod;
}
printf("%lld\n", ans);
}
int main() {
init();
int T = 1;
scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}