최소 사이클 길이의 기댓값

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

요약

N과 소수 P가 주어졌을 때, 1부터 N까지 수의 무작위 순열에서 가장 짧은 사이클 길이의 기댓값을 기약분수로 구해 P로 나눈 나머지를 출력합니다.

문제

양의 정수 $N$ 이 주어진다. 1부터 $N$ 까지의 정수를 나열한 순열들 중에서 최소 사이클 길이의 기댓값을 구하라. 모든 순열이 나올 확률은 같다.

입력은 한 줄이며, 두 정수 $N$ 과 $P$ ( $1 \le N \le 10^4$ , $10^4 < P \le 10^9 + 33$ )가 주어진다. $P$ 는 소수임이 보장된다.

기댓값을 기약분수 $\frac{A}{B}$ 로 나타낸다. $P$ 는 주어진 소수이며, $\gcd(B, P) = 1$ 임이 보장된다. $A \cdot B^{-1} \mod P$ 를 한 줄에 출력하라.