26246번 - Expected length of the minimum cycle 다국어

문제

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.

제한

힌트