Problem 3901: Up-Right

We imagine the infinite 2D plane. We define an up-right path as a path that uses only steps of type up (from the point $(x, y)$ to the point $(x, y+1)$ ), right (from the point $(x, y)$ to the point $(x+1, y)$ ), or up-right (from the point $(x, y)$ to the point $(x+1, y+1)$ ). For example, a valid path is the following: $(0, 0)$ , $(0, 1)$ , $(1, 2)$ , $(2, 2)$ .

Task

You are given $Q$ queries, and for each query the numbers $N$ , $M$ , and $K$ . How many paths exist from the point $(0, 0)$ to the point $(N, M)$ , knowing that we must use exactly $K$ up-right steps?

Input data

The first line contains the natural number $Q$ , with the meaning given in the statement.

Each of the next $Q$ lines contains a triplet of $3$ natural numbers separated by spaces, $N$ , $M$ , and $K$ , with the meaning given in the statement.

Output data

Line $i$ should contain the answer for query $i$ , modulo $1\ 000\ 000\ 007$ .

Constraints and clarifications

$1 \leq Q \leq 1 \ 000 \ 000$ ;
$1 \leq N, M \leq 1\ 000\ 000$ ;
$0 \leq K \leq \min(N, M)$ ;
Due to the very large input set, it is recommended to use fastio.
For tests worth $10$ points: $Q \leq 5; N, M, K \leq 4$ ;
For other tests worth $20$ points: $Q \leq 100\ 000; N, M \leq 2\ 000; K = 0$ ;
For other tests worth $20$ points: $Q \leq 100\ 000; N, M \leq 100\ 000; K = 0$ ;
For other tests worth $20$ points: $Q \leq 100\ 000; N, M, K \leq 100\ 000$ ;
For other tests worth $30$ points: no additional constraints.

Example

stdin

8
2 2 1
3 3 0
3 3 1
3 3 2
3 3 3
10 15 8
1000 2000 1000
100000 200000 100000

stdout

Explanation

The solutions for the first query are illustrated below:

Up-Right