Cho một mảnh vườn kích thước MxN đượ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 7 màu sau đây: đỏ, cam, vàng, lục, lam, chàm, tím. Để đảm bảo tính 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 đảm bảo tính 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.

Dữ liệu

- Gồm một số dòng, mỗi dòng ghi ba số M, N, k.

Kết quả

- Gồm một số dòng ghi các kết quả tương ứng, lấy mod 2370823708.

Ví dụ

Dữ liệu:
1 7 7

Kết quả:
5040

Giới hạn

- 1 ≤ M, N ≤ 10¹⁵.
- Số dòng trong Input không vượt quá 5000.