N-Rook II

Time limit2sMemory limit128 MB

Summary

Count placements of K rooks on an N by M board so each rook is attacked by at most one other rook, modulo 1,000,001.

Level: Hard8 of 10
Topics: Combinatorics, Math
Solved: No attempts yet

Problem

At most one rook may be placed on each square of a chessboard. A rook can attack another rook in the same row or the same column.

You want to place K rooks on an N × M chessboard. Count the number of placements in which each rook is attacked by at most one other rook. A rook may also be attacked by no other rooks.

Input

The first line contains N, the number of rows of the chessboard.

The second line contains M, the number of columns of the chessboard.

The third line contains K, the number of rooks to place.

Output

Print the number of ways to place K rooks on an N × M chessboard so that each rook is attacked by at most one other rook, modulo 1,000,001.

Constraints

1 ≤ N, M ≤ 100
1 ≤ K ≤ 100

Examples4

Example 1
Input
```
2
3
3
```
Expected output
```
6
```
Example 2
Input
```
4
5
2
```
Expected output
```
190
```
Example 3
Input
```
6
7
20
```
Expected output
```
0
```
Example 4
Input
```
23
37
39
```
Expected output
```
288688
```