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.

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.

Balanced Subsequences

Examples