Watson gives a 2-D grid to Sherlock. Rows are numbered 1 to N from top to bottom and columns are numbered 1 to M from left to right. Sherlock is at position (1,1) right now and he is free to face any direction before he starts to move. He needs to reach (N,M). In one step, he can either move downwards or rightwards. Also, he cannot make more than K turns during his whole journey.

There are two possible scenarios when a turn can occur at point (i, j):

Turns Right: (i-1, j)  ->  (i, j)  ->  (i, j+1)
                      Down        Right

Turns Down:  (i, j-1)  ->  (i, j)  ->  (i+1, j)
                     Right        Dowm

Given N, M and K, help him by printing the number of ways to reach (N,M) with at most K turns. As this value can be very large, print the answer modulo (10⁹ + 7).

Input
First line contains T, the number of testcases. Then T lines follow, where each line represents a test case. Each testcase consists of three space separated integers, N M K, where (N, M) is the final location and K is the maximum number of allowed turns.

Output
For each testcase, print the required answer in one line.

Constraints
1 ≤ T ≤ 10
1 ≤ N, M ≤ 100
0 ≤ K ≤ 100

Note

1. He can take at most K turns.
2. He is free to face any direction before starting from (1, 1).

Sample Input

3
2 2 3
2 3 1
4 4 4

Sample Output

2
2
18

Sample explanation
Test Case #00: There is no way to reach (2, 2) with 0, 2 or 3 turns. He will always reach (2, 2) with 1 turn only. There are two ways shown below:

1. He starts from (1, 1) facing right and moves to (1, 2). Then he faces down and moves to (2, 2).
2. He starts from (1, 1) facing down and moves to (2, 1). Then he turns right and moves to (2, 2).

Test Case #01: He can't reach (2, 3) with 0 turns. There are only two ways to reach (2, 3) with exactly 1 turn.

1. He starts from (1, 1) facing down and moves to (2, 1). Then he turns right and takes two steps forward to reach (2, 3).
2. He starts from (1, 1) facing right and moves two steps forward to reach (1, 3). Then he turns down and proceeds one step to (2, 3).

Test Case #02: There are 0 ways with 0 turn, 2 ways with 1 turn, 4 ways with 2 turns, 8 ways with 3 turns and 4 ways with 4 turns to reach (4, 4).

Tested by: Ashutosh Singla, Abhiranjan