팀 나누기

시간 제한1초메모리 제한256 MB

요약

n명이 각각 빨강, 파랑, 관전을 같은 확률로 고를 때 빨강이 이길 확률에 3^n을 곱한 값을 소수 p로 나눈 나머지를 구한다.

난이도: 어려움10점 중 8점
유형: 조합론, 수학, 정수론, 동적 계획법
정답자: 아직 제출이 없습니다

문제

$n$ 명으로 이루어진 회사가 게임을 하려고 한다. 각 사람은 빨간 팀에 들어가거나, 파란 팀에 들어가거나, 관전자가 될 수 있다. 각 사람은 독립적으로 셋 중 하나를 같은 확률로 선택한다. 더 많은 사람이 있는 팀이 이기고, 두 팀의 인원이 같으면 무승부가 된다. 빨간 팀이 이길 확률을 $t$ 라고 하자. $(t \cdot 3^{n}) \bmod p$ 를 구하라. 단, $p$ 는 소수이다.

입력

첫째 줄에 두 정수 $n$ 과 $p$ 가 주어진다. ( $1 \le n \le 10^{18}$ , $5 \le p < 10^{6}$ , $p$ 는 소수)

출력

문제의 답을 나타내는 정수 하나를 출력한다.

예제2

예제 1
입력
```
5 5
```
예상 출력
```
1
```
예제 2
입력
```
5 7
```
예상 출력
```
5
```