# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

# Walk on the Grid

By Hasinur_ · Limits 1s, 512 MB

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

InputOutput
2
1 1 1
10 10 10

1
3780


### Statistics

35% Solution Ratio

sansaquaEarliest, 8M ago

BigBagFastest, 0.1s

Matrix.codeLightest, 3.1 MB

amurtoShortest, 2075B