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×CR\times C where R=R = Number of rows and C=C = Number of columns. You shall walk on the grid and you can only move from (X,Y)(X,Y) cell to (X+1,Y)(X+1,Y) or (X,Y+1)(X,Y+1) cell. You shall walk exactly LL cells on the way.

Let F(A,B)F(A,B) = Number of ways you can choose a A×BA\times B sized subgrid from the grid such that you have to travel exactly LL cells including the starting cell to reach the bottom-right cell from the top-left cell of the subgrid.

Let G(A,B)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×BA\times B sized subgrid. Note that, G(A,B) depends on the value of A and B only.

You have to to choose such AA and BB that the value of F(A,B)F(A,B)×\times G(A,B)G(A,B) is maximum.

Input

First line of the input will contain a positive integer number TT (1T2×105)(1\leq T \leq 2\times 10^5).

Each of the next TT lines will contain three positive integers RR (1R105)(1\leq R \leq 10^5), CC (1C105)(1\leq C \leq 10^5) and LL (1L105)(1\leq L \leq 10^5).

Output

For each case you have to print maximum value of F(A,B)F(A,B)×\times G(A,B)G(A,B) modulo (109+7)(10^9 + 7) in a new line.

Sample

InputOutput
2
1 1 1
10 10 10
1
3780

Discussion

Statistics


35% Solution Ratio

sansaquaEarliest, 8M ago

BigBagFastest, 0.1s

Matrix.codeLightest, 3.1 MB

amurtoShortest, 2075B

Submit

Login to submit

Editorial

Alternate Writer upobir(Sabbir Rahman) came up with a nice solution. If we choose A and B such that ...

Related Contests

Toph uses cookies. By continuing you agree to our Cookie Policy.