Special Tables

Time limit2sMemory limit512 MB

Summary

Count the number of N by M tables with entries from 1 to C in which all rows are distinct and all columns are distinct, modulo 1e9+7.

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

Problem

Jungyu likes tables filled with integers. He calls a table special when it satisfies all four conditions below.

The table has $N$ rows and $M$ columns.
Each cell holds one natural number that is at least $1$ and at most $C$ .
For any two different rows $r_1$ and $r_2$ , there is at least one column $c$ such that the cells $(r_1, c)$ and $(r_2, c)$ hold different numbers.
For any two different columns $c_1$ and $c_2$ , there is at least one row $r$ such that the cells $(r, c_1)$ and $(r, c_2)$ hold different numbers.

Given $N$ , $M$ , and $C$ , write a program that counts the special tables.

Input

The first line contains $N$ , $M$ , and $C$ . ( $1 \le N, M, C \le 4000$ )

Output

Print the number of special tables modulo 1,000,000,007.

Note

For $N = M = C = 2$ the ten special tables are listed below. Each vertical pair of two-digit numbers is one table: the upper one is the first row and the lower one is the second row.

11  11  12  21  22  22  21  12  12  21
12  21  11  11  21  12  22  22  21  12

Examples6

Example 1
Input
```
2 2 2
```
Expected output
```
10
```
Example 2
Input
```
1 1 4000
```
Expected output
```
4000
```
Example 3
Input
```
2 3 5
```
Expected output
```
13740
```
Example 4
Input
```
4000 1 4000
```
Expected output
```
593395757
```
Example 5
Input
```
5 5 1
```
Expected output
```
0
```
Example 6
Input
```
4000 4000 4000
```
Expected output
```
237003303
```