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