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 atleast 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

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

Sample 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:0.256s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC VB.NET
Resource:own problem