ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

2126. Partition into Teams

Time limit: 1.0 second
Memory limit: 64 MB
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.

Input

The only line of the input contains two integers n and p (1 ≤ n ≤ 1018, 5 ≤ p < 106, p is prime).

Output

Print one integer: the answer to the problem.

Samples

inputoutput
5 5
1
5 7
5
Problem Author: Alexander Zimin
Problem Source: Petrozavodsk Summer 2018. t.me/umnik_team Contest