18954번 - Partition into Teams 다국어

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.