시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 512 MB 3 3 3 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.