29257번 - 하늘의 타일링

문제

최근 이카로스는 비어있는 $N \times M$ 격자에서 1ドル \times 2$ 모양의 도미노와 2ドル \times 1$ 모양의 도미노로 격자를 빈틈없이 채우는 도미노 타일링의 가짓수를 계산하는 방법을 공부했습니다.

하지만 배운 내용을 실험하고자 직접 만든 격자를 님프가 날아와 둥글게 말아서 각기둥 모양으로 만들어버렸습니다. 격자를 다시 만들고자 했지만 더 이상 재료가 없어 만들 수 없어 상심에 빠져 있던 찰나, 이카로스는 각기둥 모양의 격자에서도 타일링의 가짓수를 충분히 구할 수 있다고 생각했습니다. 그렇지만 배운 내용으로 이를 계산하기는 역부족이었기에 여러분에게 이 문제를 해결해달라고 부탁했습니다.

이때 격자는 격자의 세로 방향의 양 끝이 서로 맞닿게 말려있습니다.

격자를 채울 도미노들을 가지러 간 이카로스를 대신하여 $N \times M$ 격자를 말아 만든 각기둥 모양 격자의 도미노 타일링의 가짓수를 제곱한 값을 구해주세요. 각기둥을 회전했을 때 같아지는 타일링이라도 매번 세야 합니다.

입력

첫 번째 줄에 처음 격자의 세로 길이와 가로 길이를 나타내는 $N$과 $M$ 그리고 소수 $P$가 공백으로 구분되어 주어집니다. (1ドル\leq N \leq 10^{18},ドル 3ドル \leq M \leq 45,ドル 2ドル \leq P < 10^{9}$)

출력

각기둥 모양 격자의 도미노 타일링의 가짓수를 제곱한 값을 $P$로 나눈 나머지를 출력합니다.

제한

힌트