There is a grid of size $R\times C$ where $R =$ Number of rows and $C =$ Number of columns. You shall walk on the grid and you can only move from $(X,Y)$ cell to $(X+1,Y)$ or $(X,Y+1)$ cell. You shall walk exactly $L$ cells on the way.

Let $F(A,B)$ = Number of ways you can choose a $A\times B$ sized subgrid from the grid such that you have to travel exactly $L$ cells including the starting cell to reach the bottom-right cell from the top-left cell of the subgrid.

Let $G(A,B)$ = Number of ways you you can walk from the top-left cell to the bottom-right cell of the previously choosen $A\times B$ sized subgrid. Note that, G(A,B) depends on the value of A and B only.

You have to to choose such $A$ and $B$ that the value of $F(A,B)$$\times$ $G(A,B)$ is maximum.

Input

First line of the input will contain a positive integer number $T$ $(1\leq T \leq 2\times 10^5)$.

Each of the next $T$ lines will contain three positive integers $R$ $(1\leq R \leq 10^5)$, $C$ $(1\leq C \leq 10^5)$ and $L$ $(1\leq L \leq 10^5)$.

Output

For each case you have to print maximum value of $F(A,B)$$\times$ $G(A,B)$ modulo $(10^9 + 7)$ in a new line.

Sample

Input	Output
2 1 1 1 10 10 10	1 3780