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)
Turns Down: (i, j-1) -> (i, j) -> (i+1, j)
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 (109 + 7).
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.
For each testcase, print the required answer in one line.
1 ≤ T ≤ 10
1 ≤ N, M ≤ 100
0 ≤ K ≤ 100
He can take at mostK turns.
He is free to face any direction before starting from (1, 1).
2 2 3
2 3 1
4 4 4
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:
He starts from (1, 1) facing right and moves to (1, 2). Then he faces down and moves to (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.
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).
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).