Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

D. Balanced Subsequences
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard 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 2k. Since the answer can be large calculate it modulo 1000000007 (109+7).

Input

Each test contains multiple test cases. The first line contains the number of test cases t (1t3103). Description of the test cases follows.

The first line of each test case contains three integers n, m and k (1n,m,k2103)

Output

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

Example
Input
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.