Lát phòng hợp mốt

Sau khi có kết quả thi Duyên Hải Đồng Bằng Bắc Bộ năm 2022, cô S quyết định ăn mừng bằng cách lát lại sàn phòng học Đội tuyển Tin. Để sàn nhà sau khi lát hợp mốt, cô S quyết định lát sàn nhà bằng các viên gạch hình vuông kích cỡ $1\times 1$, mỗi viên gạch có màu trắng hoặc đen. Ngoài ra, trong bốn viên gạch bất kì tạo thành một hình vuông $2\times 2$ phải có ít nhất một viên gạch màu đen và một viên gạch màu trắng.

Giả sử phòng học Đội tuyển Tin của cô S có kích cỡ $3\times 3$. Ký hiệu B là gạch đen, W là gạch trắng, mỗi cách lát viết thành ba hàng từ trên xuống. Khi đó các cách lát sau là hợp mốt:

• WWW / WBW / WWW (chỉ viên gạch chính giữa màu đen);
• BWB / WWW / BWB (bốn viên gạch ở góc màu đen);
• WBW / BWB / WBW (xen kẽ như bàn cờ, viên gạch ở góc màu trắng);

và các cách lát sau là không hợp mốt:

• WWW / WWW / WWW (toàn trắng);
• BWW / WWW / BWB (hình vuông $2\times 2$ ở góc trên bên phải toàn trắng);
• WBB / WBB / WWW (hình vuông $2\times 2$ ở góc trên bên phải toàn đen).

Khi đang lát gạch, cô S tự dưng nghĩ ra bài toán sau: biết kích cỡ phòng học Đội tuyển Tin là $N\times M$ ($N$ hàng, $M$ cột), hãy tính phần dư khi chia số cách lát phòng học hợp mốt cho $P$. Hai cách lát là khác nhau nếu có ít nhất một vị trí mà hai viên gạch ở đó khác màu.

Dữ liệu vào

Một dòng duy nhất chứa ba số nguyên $N$, $M$, $P$ ($1\le N\le {10}^{200}$; $1\le M\le 5$; $1\le P\le 10000$). Số $N$ được viết không có chữ số $0$ ở đầu và có thể có tới $201$ chữ số.

Dữ liệu ra

Một dòng duy nhất chứa một số nguyên là phần dư khi chia số cách lát phòng học hợp mốt cho $P$.

Ràng buộc

• $1\le N\le {10}^{200}$
• $1\le M\le 5$
• $1\le P\le 10000$

Subtasks

Điểm được tính theo từng test.

• Subtask 1 ($30\%$ số test): $N\le {10}^{20}$; $P\le 100$.
• Subtask 2 ($30\%$ số test): $N\le {10}^{100}$; $P\le 1000$.
• Subtask 3 ($40\%$ số test): không có ràng buộc gì thêm.

Ví dụ