Busy Beaver는 그래프 이론 수업을 듣고 있는데, 선생님께서 특별한 조건을 만족하는 그래프의 개수를 세어보라는 숙제를 내주셨습니다. 그래프 개수를 세는 이 문제를 해결하도록 도와주세요!
$P$를 홀수인 소수, $N$을 양의 정수라고 합시다. $NP$개의 정점을 가진 무방향 라벨링된 단순 그래프 중에서 길이가 $P$인 단순 사이클을 포함하지 않는 그래프의 개수를 구하세요. 정답을 $P$로 나눈 나머지를 출력하세요. 이 문제에서 $P$가 반복해서 사용된다는 점에 유의하세요!
무방향 그래프에서 단순 사이클이란 정점을 한 번 이상 방문하지 않는 사이클을 의미합니다.
입력
입력은 한 줄에 두 정수 $P$ ($3 \le P < 5000$)와 $N$ ($1 \le N \le 10^9$)이 주어집니다. $P$는 홀수인 소수입니다.
출력
$P$로 나눈 나머지를 한 정수로 출력하세요.
채점
- (25점) $N \le P$ 이고 $P \le 500$.
- (25점) $N \le P$.
- (25점) $P \le 500$.
- (25점) 추가 제약 조건 없음.
예제
예제 입력 1
3 1
예제 출력 1
1
예제 입력 2
5 4
예제 출력 2
1
예제 입력 3
479 166
예제 출력 3
344
참고
첫 번째 예제에서는 $1 \cdot 3 = 3$개의 정점을 가진 라벨링된 그래프 중에서 길이가 3인 단순 사이클을 포함하지 않는 그래프의 개수를 셉니다. 정점 3개를 가진 그래프의 가능한 간선 조합은 총 $2^{\binom{3}{2}} = 2^3 = 8$개입니다. 이 중 길이가 3인 단순 사이클(삼각형)을 포함하는 그래프는 1개이므로, 이를 제외하면 $8 - 1 = 7$가지 경우가 존재합니다. 따라서 7을 3으로 나눈 나머지는 1입니다.