Petya và tô màu

Cho một bảng chữ nhật kích thước $n\times m$ ($n$ hàng, $m$ cột). Ta tô màu mỗi ô của bảng bằng một trong $k$ màu.

Một cách tô màu được gọi là hợp lệ nếu nó thỏa mãn điều kiện sau: với mọi đường thẳng đứng chạy dọc theo các đường lưới và chia bảng thành hai phần đều khác rỗng, số màu phân biệt xuất hiện ở phần bên trái phải bằng số màu phân biệt xuất hiện ở phần bên phải.

Hãy đếm số cách tô màu hợp lệ. Vì kết quả có thể rất lớn, in ra kết quả theo modulo ${10}^9+7$.

Dữ liệu vào

Một dòng chứa ba số nguyên $n$, $m$ và $k$: số hàng, số cột và số màu.

Dữ liệu ra

In ra một số nguyên duy nhất: số cách tô màu hợp lệ theo modulo ${10}^9+7$.

Ràng buộc

• $1\le n,m\le 1000$
• $1\le k\le {10}^6$

Ví dụ