CF1924D.Balanced Subsequences

A sequence of brackets is called balanced if one can turn it into a valid math expression by adding characters '+' and '1'. For example, sequences '(())()', '()', and '(()(()))' are balanced, while ')(', '(()', and '(()))(' are not.

A subsequence is a sequence that can be derived from the given sequence by deleting zero or more elements without changing the order of the remaining elements.

You are given three integers $n$, $m$ and $k$. Find the number of sequences consisting of $n$ '(' and $m$ ')', such that the longest balanced subsequence is of length $2 \cdot k$. Since the answer can be large calculate it modulo $1\,000\,000\,007$ ($10^9 + 7$).

如果可以通过添加字符 '+' 和 '1' 将一个括号序列变为合法的数学表达式，则称该括号序列为平衡的。例如，序列 (())()、() 和 (()(())) 是平衡的，而 )(、(() 和 (()))( 则不是。

子序列是指从给定序列中删除零个或多个元素（不改变剩余元素的相对顺序）所得到的序列。

给定三个整数 $n$、$m$ 和 $k$。求由 $n$ 个 '(' 和 $m$ 个 ')' 组成的序列中，其最长平衡子序列的长度恰好为 $2 \cdot k$ 的序列个数。由于答案可能很大，请对 $1\,000\,000\,007$（即 $10^9 + 7$）取模。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 3 \cdot 10^3$). Description of the test cases follows.

The first line of each test case contains three integers $n$, $m$ and $k$ ($1 \le n, m, k \le 2 \cdot 10^3$)

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 3 \cdot 10^3$）。随后是测试用例的描述。

每个测试用例的第一行包含三个整数 $n$、$m$ 和 $k$（$1 \le n, m, k \le 2 \cdot 10^3$）

For each test case, print one integer — the answer to the problem.

对于每个测试用例，输出一个整数——即该问题的答案。

For the first test case "()()", "(())" are the $2$ sequences

For the second test case no sequence is possible.

For the third test case ")((()", ")(()(", ")()((", "())((" are the $4$ sequences.

对于第一个测试用例，"()()" 和 "(())" 是 $2$ 个合法序列。

对于第二个测试用例，不存在任何合法序列。

对于第三个测试用例，")((()"、")(()("、")()((" 和 "())((" 是 $4$ 个合法序列。