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.
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)$
.
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.
Input | Output |
---|---|
2 1 1 1 10 10 10 | 1 3780 |