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 <c1 <= m). Two rectangles are called independent if the intersection of their cell set is empty.
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.

Input

One line contains three integers n,m,k(1<=n,m<=1000, 1<=k<=6).

Output

For each test case, output the number of ways, modulo 10^9+7.

Example

Input:
2 2 4
10 10 1
Output:
1
3025
Explanation
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.

Constraints

(1<=n,m<=1000, 1<=k<=6).
Total number of test cases is around 150. Not all the test cases are included.