Cô S quyết định lát lại sàn phòng học Đội tuyển Tin bằng các viên gạch hình vuông kích thước ~1 \times 1~, mỗi viên gạch có màu trắng hoặc đen.

Để sàn nhà sau khi lát hợp mốt, 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.

Biết phòng học Đội tuyển Tin có kích thước ~N \times 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

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)~.

Output

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

Scoring

Sample Input 1

2 2 5

Sample Output 1

4

Sample Input 2

3 3 23

Sample Output 2

0