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 · 3ⁿ) mod p, where p is prime.

The only line of the input contains two integers n and p (1 ≤ n ≤ 10¹⁸, 5 ≤ p < 10⁶, p is prime).

Print one integer: the answer to the problem.