시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 (추가 시간 없음) 1024 MB32266.667%

문제

You are given a positive integer $N$, find the expected length of the minimum cycle in permutation of integers from $1$ to $N$. All permutations are equiprobable.

Consider the answer is an irreducible fraction $\frac{A}{B}$. Output $A \cdot B^{-1} \mod P$, where $P$ is a given prime number. It is guaranteed that $gcd(B, P) = 1$.

입력

The only line of input contains two integers $N$ and $P$ ($1 \le N \le 10^4$, $10^4 < P \le 10^9 + 33$). It's guaranteed that $P$ is a prime number.

출력

Output the answer to the problem in a single line.

예제 입력 1

2 1000000007

예제 출력 1

500000005

예제 입력 2

3 1000000007

예제 출력 2

666666673