Rock-Paper-Scissors

Time limit2sMemory limit512 MB

Summary

Given n rounds of random rock-paper-scissors and p prime, compute the expected GCD score of the win counts times 3^(2n), modulo p.

Level: Medium7 of 10
Topics: Math, Number theory, Combinatorics, Probability
Solved: No attempts yet

Statement

Alice and Bob are going to play the famous game "Rock-Paper-Scissors". Both of them dislike thinking much, so both use a random strategy: each picks rock, paper, or scissors with equal probability.

They play the game $n$ times and then compute a score $s$ as follows. If Alice won $a$ times, Bob won $b$ times, and the remaining $n - a - b$ games were draws, the score is the greatest common divisor of $a$ and $b$ . If $a$ or $b$ is $0$ , the greatest common divisor of $a$ and $b$ is defined as $a + b$ .

Calculate the expected value of $s \cdot 3^{2 n}$ . The answer is always an integer. Because it may be very large, print its remainder modulo $p$ .

Input

The input contains two integers $n$ and $p$ ( $1 \le n \le 10^5$ , $10^8 \le p \le 10^9$ , $p$ is prime).

Output

Print a single integer: the answer modulo $p$ .

Examples2

Example 1
Input
```
1 998244353
```
Expected output
```
6
```
Example 2
Input
```
2 998244353
```
Expected output
```
90
```