Cho một bảng hình chữ nhật kích thước ~M \times N~ và bốn loại bi: xanh, đỏ, tím, vàng. Số lượng bi của mỗi loại là không giới hạn.

Hai cách xếp được gọi là khác nhau nếu có ít nhất một ô chứa hai loại bi khác nhau trong hai cách xếp đó.

Yêu cầu: Hãy đếm số cách xếp bi vào bảng sao cho mỗi ô chứa đúng một viên bi và trên mỗi hàng có ít nhất ~k~ loại bi khác nhau.

Vì kết quả có thể rất lớn, hãy in kết quả lấy phần dư khi chia cho ~10^9+7~.

Input

Một dòng duy nhất gồm ba số nguyên dương ~M,N,k~ ~(1 \le M,N \le 10^6;\ 1 \le k \le 4)~.

Output

Một số nguyên duy nhất là số cách xếp thỏa mãn yêu cầu, lấy phần dư khi chia cho ~10^9+7~.

Scoring

Sample Input 1

1 2 1

Sample Output 1

16