Special Tables

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.

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

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

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