311034: CF1924D. Balanced Subsequences

D. Balanced Subsequencestime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

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$).

Input

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$)

Output

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

ExampleInput

3
2 2 2
3 2 3
3 2 1

Output

2
0
4

Note

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.

题目大意：
一个括号序列如果可以通过添加'+'和'1'字符变成一个有效的数学表达式，则该序列被称为平衡的。例如，序列'(())()', '()', 和'(()(()))'是平衡的，而')(', '(()', 和'(()))('不是。

一个子序列是通过删除零个或多个元素但不改变剩余元素的顺序而从给定序列派生出来的序列。

给定三个整数n、m和k，找出由n个'('和m个')'组成的序列的数量，使得最长的平衡子序列的长度为2*k。由于答案可能很大，计算其对1,000,000,007（10^9 + 7）取模的结果。

输入输出数据格式：
输入：
每个测试包含多个测试案例。第一行包含测试案例的数量t（1 ≤ t ≤ 3 * 10^3）。接下来是每个测试案例的描述。
每个测试案例的第一行包含三个整数n、m和k（1 ≤ n, m, k ≤ 2 * 10^3）。

输出：
对于每个测试案例，打印一个整数——问题的答案。

示例：
输入：
3
2 2 2
3 2 3
3 2 1

输出：
2
0
4

注意：
第一个测试案例中")()"和"(())"是2个序列。
第二个测试案例中没有可能的序列。
第三个测试案例中"((()", ")(()", ")()("和")())("是4个序列。题目大意： 一个括号序列如果可以通过添加'+'和'1'字符变成一个有效的数学表达式，则该序列被称为平衡的。例如，序列'(())()', '()', 和'(()(()))'是平衡的，而')(', '(()', 和'(()))('不是。 一个子序列是通过删除零个或多个元素但不改变剩余元素的顺序而从给定序列派生出来的序列。 给定三个整数n、m和k，找出由n个'('和m个')'组成的序列的数量，使得最长的平衡子序列的长度为2*k。由于答案可能很大，计算其对1,000,000,007（10^9 + 7）取模的结果。 输入输出数据格式： 输入： 每个测试包含多个测试案例。第一行包含测试案例的数量t（1 ≤ t ≤ 3 * 10^3）。接下来是每个测试案例的描述。 每个测试案例的第一行包含三个整数n、m和k（1 ≤ n, m, k ≤ 2 * 10^3）。 输出： 对于每个测试案例，打印一个整数——问题的答案。 示例： 输入： 3 2 2 2 3 2 3 3 2 1 输出： 2 0 4 注意： 第一个测试案例中")()"和"(())"是2个序列。 第二个测试案例中没有可能的序列。 第三个测试案例中"((()", ")(()", ")()("和")())("是4个序列。