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^{n}) *mod* *p*, where *p* is prime.

### Input

The only line of the input contains two integers *n* and *p* (1 ≤ *n* ≤ 10^{18}, 5 ≤ *p* < 10^{6}, *p* is prime).

### Output

Print one integer: the answer to the problem.

### Samples

**Problem Author: **Alexander Zimin

**Problem Source: **Petrozavodsk Summer 2018. t.me/umnik_team Contest