시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 512 MB 6 6 5 100.000%

문제

A tree is an undirected graph in which any two vertices are connected by exactly one path. One tree is chosen uniformly at random among all labeled trees with $n$ vertices. Define the cost of the tree as

$\min_{i=1}^{n}{\sum_{j=1}^{n}{dist(i,j)}}$

where $dist(i, j)$ is the number of edges in the simple path from vertex $i$ to vertex $j$. Find the expected value of cost of a chosen tree.

입력

The only line contains two integers $n$ and $m$ ($3 \le n \le 5000$, $900 000 011 \le m \le 1 000 000 007$, $m$ is prime) separated by a single space.

출력

It can be shown that the answer can be represented as an irreducible fraction $\frac{P}{Q}$, where $P$ and $Q$ are positive coprime integers and $Q \not\equiv 0$ (mod $m$). Print a single integer $X = P \cdot Q^{−1}$ (mod $m$) ($0 \le X < m$), where $Q^{−1}$ is the inverse of $Q$ modulo $m$.

예제 입력 1

4 900000011


예제 출력 1

675000012


예제 입력 2

7 1000000007


예제 출력 2

363182020


예제 입력 3

4999 950000017


예제 출력 3

506366868


힌트

The exact answers for the first and the second sample tests are $\frac{15}{4}$ and $\frac{23 916}{2401}$, respectively.