GRIDCOIN - Placing Coins on a Grid

no tags 

In how many ways can R coins be placed on an N × M grid such that each row and each column have at least 1 coin?

Input

The first line contains the number of test cases T. T lines follow containing 3 integers: N, M and R. (1 ≤ T ≤ 100. 1 ≤ N, M ≤ 200. 1 ≤ R ≤ N × M)

Output

Output T lines, one for each test case, containing the output for the corresponding test case. Output all values modulo 1000000007.

Example

Input:
3
1 1 1
2 1 1
2 3 3

Output:
1
0
6

hide comments
Varun Jalan: 2010-09-28 07:06:15

yes

Madhusudhanan D`: 2010-09-28 07:06:15

Are the coins identical?

Varun Jalan: 2010-09-28 07:06:15

no

Madhusudhanan D`: 2010-09-28 07:06:15

Can a grid contain more than 1 coin?


Added by:Varun Jalan
Date:2010-09-12
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC VB.NET
Resource:own problem