You are given three integers \(Z, O, K\).

Your task is to determine the number of distinct sequences of length \(Z + O\) that contains exactly \(Z\) zeroes and \(O\) ones. Also, the length of longest non-decreasing subsequence in the sequence is of length \(\ge K\).

Note

• Two sequences are said to be distinct if there exists at least one index where the value of element present is different in both sequences.
• A non-decreasing subsequence of \(a\) is a sequence of integers \(a_{p_1}, a_{p_2}, ... , a_{p_k}\) where \(p_1 < p_2 < .. < p_k\) and \(a_{p_1} \le a_{p_2} \le ... \le a_{p_k}\).

Input format

• The first line contains an integer \(T\) that denotes the number of test cases.
• For each test case:
  • The first line contains three space-separated integers \(Z , O , K\).

Output format

For each test case, print the number of distinct sequences that satisfy the provided conditions.

Note: The result can be a large value, print the output in modulo \(10^9 + 7\) format.

Constraints