Partition into Teams

Time limit1sMemory limit256 MB

Summary

For n people each choosing red, blue, or spectator uniformly, compute 3^n times the probability that red wins, modulo a prime p.

Level: Hard8 of 10
Topics: Combinatorics, Math, Number theory, Dynamic programming
Solved: No attempts yet

Problem

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

Input

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).

Output

Print one integer, the answer to the problem.

Examples2

Example 1
Input
```
5 5
```
Expected output
```
1
```
Example 2
Input
```
5 7
```
Expected output
```
5
```