Chef Elie and Chef Rob finds a new hash function! Their hash function will map a binary string consisting of characters 'B' and 'E' into an integer called the hash value of the string. The pseudocode of their hash function is as below. hash(S) is the hash value of a binary string S. |S| denotes the length of S.

function hash(S):
    result = number of characters 'B' in S
    if |S| > 1:
        (S1, S2) = split(S)
        result = result + max(hash(S1), hash(S2))
    end if
    return result
end function

The function split in the above pseudocode takes a binary string S as the parameter and returns a pair of binary strings (S1, S2) such that: |S1| <= |S2|. The difference of |S1| and |S2| is at most 1. The concatenation of S1 and S2 (in that order) is S. For example, split("BBBEE") returns ("BB", "BEE"), whereas split("BEBEBE") returns ("BEB", "EBE"). You doubt that this hash function have good distribution of different hash values. So, you wonder how many different binary strings consisting of B 'B' characters and E 'E' characters that have hash value of V. Input

The first line contains a single integer T, the number of test cases. T test cases follow. Each testcase consists of a single line consisting of three integers B, E, and V. Output

For each test case, output a single line consisting the number of different binary strings satisfying the rule, modulo 1000000007. Constraints

1 <= T <= 1000 0 <= B <= 50 0 <= E <= 50 0 <= V <= 1000