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 n×m 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⁹+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 2×2 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.