시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 1 1 1 100.000%

문제

A company of $n$ people decided to play a game. Each person can either join red team, join blue team, or become a spectator. Each person makes a decision independently and picks one of the three options with equal probability. The team which gets more players will win the game; the game ends in a draw in case both teams have an equal number of players. Let us denote the probability of red team winning by $t$. Find $(t \cdot 3^{n}) \bmod p$, where $p$ is prime.

입력

The only line of the input contains two integers $n$ and $p$ ($1 \le n \le 10^{18}$, $5 \le p < 10^{6}$, $p$ is prime).

출력

Print one integer: the answer to the problem.

예제 입력 1

5 5

예제 출력 1

1

예제 입력 2

5 7

예제 출력 2

5