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,Y+1)$ cell. You shall walk exactly
$L$ cells on the way.
$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.
$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
$B$ that the value of
$G(A,B)$ is maximum.
First line of the input will contain a positive integer number
$(1\leq T \leq 2\times 10^5)$.
Each of the next
$T$ lines will contain three positive integers
$(1\leq R \leq 10^5)$,
$(1\leq C \leq 10^5)$ and
$(1\leq L \leq 10^5)$.
For each case you have to print maximum value of
$(10^9 + 7)$ in a new line.
2 1 1 1 10 10 10