가위바위보

Alice와 Bob은 유명한 게임 "Rock-Paper-Scissors"를 하려고 한다. 둘 다 깊이 생각하는 것을 싫어하므로, 둘 다 무작위 전략을 쓴다. 즉, 바위, 보, 가위 중 하나를 같은 확률로 고른다.

두 사람은 게임을 $n$번 한 뒤 다음 방식으로 점수 $s$를 계산한다. Alice가 $a$번 이기고 Bob이 $b$번 이기며 나머지 $n - a - b$번은 비긴 경우, 점수 $s$는 $a$와 $b$의 최대공약수이다. $a$나 $b$가 $0$이면 $a$와 $b$의 최대공약수를 $a + b$로 정의한다.

$s \cdot 3^{2 n}$의 기댓값을 구하라. 이 값은 반드시 정수가 된다. 값이 매우 클 수 있으므로 $p$로 나눈 나머지를 구한다.

두 정수 $n$과 $p$가 주어진다 ($1 \le n \le 10^5$, $10^8 \le p \le 10^9$, $p$는 소수이다).

정수 하나를 출력한다. 답을 $p$로 나눈 나머지이다.