L. Drawing Rectangles
time limit per test
2 s
memory limit per test
256 megabytes
input
standard input
output
standard output

As an aspiring artist, you prepare to impress the world with another masterpiece on an $$$n \times m$$$ canvas.

To make it more impactful, you will close your eyes and paint $$$k$$$ non-degenerate rectangles one after another in a way that, for each rectangle, its edges are parallel to the sides of the canvas and have integer distances from them, and the rectangles themselves are chosen uniformly at random from the set of all valid rectangles, independently from each other.

You are certain that the impact of the painting on the audience will be equal to the number of rectangles (out of the $$$k$$$ that you have painted) that are fully visible and unobscured by other rectangles.

You want to find the expected value of the impact of your painting over all possible ways to select $$$k$$$ rectangles. Assume that if two rectangles only share an edge, they do not obscure each other.

Input

The only line of the input contains three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$1 \leq n,m,k \leq 42$$$).

Output

Let $$$\frac{p}{q}$$$ be the reduced fraction representing the expected impact of your painting.

Print $$$p \cdot q^{-1} \pmod{10^9+7}$$$. It can be proven that $$$q \not \equiv 0 \pmod{10^9+7}$$$.

Examples
Input
1 2 2
Output
222222225
Input
3 4 5
Output
51141916
Note

In the first example, the answer is $$$\frac{11}{9} \approx 1.22$$$, as there are $$$3 \cdot 3 = 9$$$ ways to paint two rectangles, but only two of such ways would allow presenting both rectangles unobscured.