树是一个无向图，其中任意两个顶点之间都有且仅有一条路径。在所有 $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}$ 是 $Q$ 模 $m$ 的逆元。

样例

样例输入 1

4 900000011

样例输出 1

675000012

样例输入 2

7 1000000007

样例输出 2

363182020

样例输入 3

4999 950000017

样例输出 3

506366868

说明

第一个和第二个样例测试的精确答案分别为 $\frac{15}{4}$ 和 $\frac{23\,916}{2401}$。