스시 디너

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

요약

2부터 n까지의 수에서 부분집합 X, Y를 고를 때, X의 모든 원소가 Y의 모든 원소와 서로소인 경우의 수를 p로 나눈 나머지로 구합니다.

난이도: 보통10점 중 7점
유형: 정수론, 동적 계획법, 비트 연산
정답자: 아직 제출이 없습니다

문제

$X, Y \subseteq \{2, 3, \dots, n\}$ 인 두 부분집합 $X, Y$ 를 고르는 방법의 수를 구하라. $x \in X$ 이고 $y \in Y$ 인 어떤 쌍도 $x$ 와 $y$ 가 서로소가 아니면 안 된다. $X$ 와 $Y$ 는 공집합일 수 있다. 조건을 만족하는 방법의 수를 $p$ 로 나눈 나머지를 출력하라.

입력

정수 $n$ 과 모듈러 값 $p$ 가 공백으로 구분되어 주어진다.

출력

위 조건을 만족하는 부분집합의 쌍 $X, Y \subseteq \{2, 3, \dots, n\}$ 의 개수를 출력하라.

제한

$2 \le n \le 500$
$0 < p \le 1\,000\,000\,000$

예제3

예제 1
입력
```
3 10000
```
예상 출력
```
9
```
예제 2
입력
```
4 10000
```
예상 출력
```
21
```
예제 3
입력
```
100 100000000
```
예상 출력
```
3107203
```