Cho một bảng kích thước ~M \times N~. George có tất cả ~K~ màu khác nhau. Cậu muốn tô màu bảng này sao cho:

Mỗi màu được sử dụng ít nhất một lần ở dòng trên cùng của bảng

~2~ ô cùng màu phải thuộc cùng ~1~ thành phần liên thông

~2~ cách tô màu được gọi là khác nhau nếu dòng trên cùng của ~2~ bảng là khác nhau. Đếm số cách tô màu có thể, lấy modulo ~10^{9} + 7~

Input

• Dòng ~1~: ~3~ số nguyên ~M~, ~N~, ~K~ (~0 < M, N, K \leq 300~)

Output

• Một dòng đưa ra số cách tô màu có thể.

Sample Input 1

4 1 2

Sample Output 1

6

Sample Input 2

4 3 2

Sample Output 2

12

Sample Input 3

4 4 10

Sample Output 3

0

Sample Input 4

14 28 14

Sample Output 4

178290591

Note

Trong test ví dụ số ~1~, ~6~ cách tô màu là "AAAB", "AABB", "ABBB", "BBBA", "BBAA" và "BAAA".

Trong test ví dụ số ~2~, có thêm ~6~ cách tô màu dòng đầu tiên. Bảng sau đây mô tả một số cách tô hợp lệ:

ABAA AABA ABBA BABB BBAB BAAB

ABBA AAAA ABAA BABB BAAB BBBB

AAAA AAAA AAAA BBBB BBBB BBBB