RECTMAT - Rectangles in a Matrix
In a matrix with n rows and m columns, (i, j) is the cell in i-th row and j-th column (0 <= i < n, 0 <= j < m). A rectangle (r0, r1, c0, c1) in a matrix is the set of cells (i, j) where r0 <= i < r1 and c0 <= j < c1. (0 <= r0 < r1 <= n, 0 <= c0 Given n, m, k, find the number of ways to choose k independent rectangles from a nxm matrix. The order of these k rectangles doesn't matter, see sample for further clarification. One line contains three integers n, m, k (1 <= n, m <= 1000, 1 <= k <= 6). For each test case, output the number of ways, modulo 10^9+7. First case: You have to find the number of ways of choosing 4 independent rectangles from a 2x2 matrix.
The only way to do this is to choose each cell as a separate rectangle. (1 <= n, m <= 1000, 1 <= k <= 6).
Total number of test cases is around 150. Not all the test cases are included.Input
Output
Example
Input:
2 2 4
10 10 1
Output:
1
3025
Explanation
Constraints
Added by: | Kunal Jain |
Date: | 2011-02-07 |
Time limit: | 7s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | CodeCraft 11 |