GRIDCOIN - Placing Coins on a Grid

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

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

hide comments
2010-09-28 07:06:15 Varun Jalan
yes
2010-09-28 07:06:15 Madhusudhanan D`
Are the coins identical?
2010-09-28 07:06:15 Varun Jalan
no
2010-09-28 07:06:15 Madhusudhanan D`
Can a grid contain more than 1 coin?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.