기댓값 비용
시간 제한3초메모리 제한512 MB
n개 정점의 레이블 트리를 균일하게 무작위로 고를 때, 한 정점에서 다른 모든 정점까지 거리 합의 최솟값에 대한 기댓값을 소수 모듈로로 구한다.
문제
트리는 임의의 두 정점을 잇는 경로가 정확히 하나인 무방향 그래프이다. 정점이 (n)개인 레이블 트리 중 하나를 균등한 확률로 고른다. 트리의 비용을 다음과 같이 정의하자.
[\min_{i=1}^{n}\sum_{j=1}^{n} dist(i,j)]
여기서 (dist(i,j))는 정점 (i)에서 정점 (j)로 가는 단순 경로의 간선 수이다. 고른 트리의 비용의 기댓값을 구하여라.
입력
첫째 줄에 두 정수 (n)과 (m)이 공백 하나를 사이에 두고 주어진다. ((3 \le n \le 5000), (900,000,011 \le m \le 1,000,000,007), (m)은 소수)
출력
답은 기약분수 (\frac{P}{Q})로 나타낼 수 있다. 여기서 (P)와 (Q)는 양의 서로소 정수이고 (Q \not\equiv 0 \pmod{m})이다. (X = P \cdot Q^{-1} \pmod{m}) ((0 \le X < m))을 출력하여라. (Q^{-1})은 (m)에 대한 (Q)의 역원이다.
힌트
첫 번째와 두 번째 예제의 정확한 답은 각각 (\frac{15}{4})와 (\frac{23,916}{2401})이다.