Cho một mảnh vườn kích thước M × N được chia thành M hàng và N cột. Mỗi ô trong vườn phải được trồng đúng một loài hoa với một trong 4 màu sau:

• Xanh
• Đỏ
• Tím
• Vàng

Để đảm bảo tính thẩm mỹ, mỗi hàng phải có ít nhất k màu hoa khác nhau.

Hai cách trồng hoa được coi là khác nhau nếu tồn tại ít nhất một ô có màu khác nhau.

Hãy đếm số cách trồng hoa thỏa mãn yêu cầu.

Do kết quả có thể rất lớn, hãy in ra phần dư của kết quả khi chia cho 1000000007.

Dữ liệu vào

Một dòng chứa ba số nguyên:

• M, N, k (1 ≤ M, N ≤ 50, 1 ≤ k ≤ 4).

Dữ liệu ra

Một số nguyên duy nhất là số cách trồng hoa thỏa mãn yêu cầu, lấy modulo 1000000007.

INPUT

2 2 2

OUTPUT

144