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.