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

Yêu cầu: Hãy đếm số cách xếp các viên bi vào bảng ~M \times N~ sao cho trên mỗi dòng phải có ít nhất ~k~ loại bi khác nhau, biết rằng hai cách xếp được gọi là khác nhau nếu có ít nhất một ô khác loại. Vì số cách rất lớn nên chỉ cần in ra phần dư của kết quả khi chia cho ~10^9 + 7~.

Input

• Gồm một dòng duy nhất ghi 3 số nguyên dương ~M, N, k~. Các số được ghi cách nhau bởi dấu cách.

Output

• Ghi ra một dòng duy nhất ghi số cách xếp thỏa mãn yêu cầu bài toán.

Sample Input 1

1 2 1

Sample Output 1

16