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 · 3n) mod p, where p is prime.
The only line of the input contains two integers n and p (1 ≤ n ≤ 1018, 5 ≤ p < 106, p is prime).
Print one integer: the answer to the problem.
Problem Author: Alexander Zimin
Problem Source: Petrozavodsk Summer 2018. t.me/umnik_team Contest