Cho một mảnh vườn kích thước ~M \times N~ được chia thành ~M~ hàng, mỗi hàng có ~N~ ô để trồng hoa. Ở mỗi ô ta có thể trồng một loài hoa có một trong 4 màu sau đây: xanh, đỏ, tím, vàng. Để đảm bảo thẩm mỹ, tất cả các ô đều phải trồng hoa và ở mỗi hàng cần có ít nhất ~k~ màu hoa khác nhau.

Yêu cầu: Hãy đếm số cách trồng hoa khác nhau mà vẫn bảo đảm thẩm mỹ. Hai cách trồng được gọi là khác nhau nếu có ít nhất một ô khác màu. Kết quả lấy phần dư khi chia cho ~10^9 + 7~.

Input

• Dòng đầu ghi 3 số ~M, N, k~ (~1 \le M, N \le 50, 1 \le k \le 4~).

Output

• Gồm một số duy nhất ghi phần dư khi chia số cách trồng hoa khác nhau cho ~1000000007~.

Sample Input 1

2 2 2

Sample Output 1

144