Walk on the Grid

Hasinur_ Criterion 2021 Round 11
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.


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.


1 1 1
10 10 10


Login to submit.



35% Solution Ratio
sansaquaEarliest, Mar '21
BigBagFastest, 0.1s
Matrix.codeLightest, 3.1 MB
amurtoShortest, 2075B
Toph uses cookies. By continuing you agree to our Cookie Policy.