D. Balanced Subsequencestime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputA 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).InputEach 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)OutputFor each test case, print one integer — the answer to the problem.ExampleInput
32 2 23 2 33 2 1Output
2
0
4
NoteFor the first test case "()()", "(())" are the 2 sequencesFor the second test case no sequence is possible.For the third test case ")((()", ")(()(", ")()((", "())((" are the 4 sequences.
32 2 23 2 33 2 1
2 0 4 
['combinatorics', 'dp', 'math', '*2700']