Trường Đại học Công nghệ Thông tin và Truyền thông (ICTU) đang chuẩn bị tổ chức "Ngày hội bảo vệ Đồ án tốt nghiệp". Hiếu là một sinh viên năm cuối cũng chuẩn bị thực hiện báo cáo đồ án này. Vì tin tưởng vào yếu tố "tâm linh" nên Hiếu quyết định sẽ quy hoạch toàn bộ chỉ số của từng phòng hội đồng bảo vệ.

Mỗi phòng được chia thành một ma trận chỗ ngồi gồm M hàng và N cột \((1 <= M, N <= 20)\). Dựa vào mật độ sinh viên, độ mát của quạt và điều hòa, cường độ ánh sáng …, mỗi ô vuông ở vị trí (i, j) được đánh giá một "chỉ số thoải mái" là \(U_{ij} \qquad (1 \le U_{ij} \le 10^9)\). Ngoài ra, vì chỉ số có thể vượt ngoài tầm kiểm soát tính toán nên cần một số nguyên P \((1 <= P <= 10^9)\) để giới hạn lại.

Để có chỗ ngồi thật sự "phong thủy" cho bài báo cáo đồ án được suôn sẻ, một lập trình viên hạng sang như Hiếu đã khoanh vùng một khu vực hình chữ nhật bất kỳ giữa các chỗ ngồi đó. Chỉ số thoải mái tối đa của hình đó được xác định như sau: \(X = ((S \bmod P) ^ V) \bmod (10^9 + 9)\)

Trong đó:

• S là tổng giá trị của V phần tử đã chọn trong hình chữ nhật.
• mod là phép chia lấy phần dư (trong các ngôn ngữ C/C++, Python, Java: biểu thị bằng toán tử %).

Yêu cầu:

Tìm giá trị X lớn nhất và in ra màn hình.

Ví dụ: Với đề bài có M = 3, N = 3, P = 5, cùng ma trận sau: 1 2 3 4 5 6 7 8 9

• Nếu chọn cả ma trận, thì \(S = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 45, V = 9\), như vậy \(X = (45 \bmod 5) \times 9 \bmod (10^9 + 9) = 0\).
• Nếu chọn hình sau: 4 5 6 7 8 9 \(S = 4 + 5 + 6 + 7 + 8 + 9 = 39\), \(V = 6\). \(X = (39 \bmod 5)^6 \bmod (10^9 + 9) = 4^6 \bmod (10^9 + 9) = 4096\). Đây là giá trị (X) lớn nhất của ma trận này.

Input:

• Dòng đầu gồm ba số nguyên dương là M, N và P.
• M dòng kế tiếp, mỗi dòng gồm N số nguyên \(U_{ij}\). Output:
• Một số nguyên duy nhất là giá trị X lớn nhất theo yêu cầu đề bài.

Input:

3 3 5
1 2 3
4 5 6
7 8 9

Output:

4096