NICE - Lát sàn

Xem dạng PDF
Gửi bài giải
Điểm: 1,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Tác giả:
Hieu Nguyen
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift

Sau khi có kết quả thi HSG Quốc gia 2017, thầy X 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, thầy X quyết định lát sàn nhà bằng các viên gạch hình vuông kích cỡ ~1 × 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×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 thầy X có kích cỡ ~3 × 3~, khi đó các cách lát sau là hợpmốt:

Screenshot from 2020-12-27 10-43-22.png

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

Screenshot from 2020-12-27 10-43-37.png

Khi đang lát gạch, thầy X 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 ×M~, hãy tính phần dư khi chia số cách lát phòng học hợp mốt cho ~P~.

Input

  • Gồm một dòng duy nhất chứa ba số nguyên ~N, M, P (1 ≤ N ≤ 10^{200}, 1 ≤ M ≤ 5, 1 ≤ P ≤ 10000)~.

Output

  • Gồm một dòng duy nhất chứa một số nguyên là kết quả của bài toán do thầy X nghĩ ra.

Sample

Input #1
2 2 5
Output #1
1
Input #2
3 3 23
Output #2
0

Problem source: Kc97ble - Free Contest 37

Bình luận

Hãy đọc nội quy trước khi bình luận.