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 |
