Bảng số

Bạn được cho một bảng số gồm \(n\) hàng và \(m\) cột. Trong mỗi ô của bảng, bạn được điền một con số từ \(1\) đến \(k\). Tuy nhiên có ràng buộc đặc biệt là trong mỗi hàng và mỗi cột của bảng thì phải chứa ít nhất \(1\) ô được điền số \(1\).

Nhiệm vụ của bạn là đếm số cách điền bảng trên sao cho thỏa mãn ràng buộc.

Input

• Dòng đầu tiên chứa ba số nguyên \(n, m, k\) \((1 \leq n, m \leq 1000, 1 \leq k \leq 10^9)\), lần lượt là số hàng, số cột và số con số có thể sử dụng để điền vào bảng.

Output

In ra số cách điền bảng trên. Vì kết quả có thể rất lớn, in ra đáp án khi chia dư cho \(10^9 + 7\).

Example

2 2 3

17

3 4 3

101089

Scoring

• Có \(20\%\) số điểm ứng với \(n \times m \le 20\).
• Có \(30\%\) số điểm ứng với \(n, m \le 500\).
• Có \(50\%\) số điểm ứng với \(n, m \le 1000\).