题目描述

某国有$\red{n}$个不同的城市，但一条道路也没有，交流非常的不方便。所以国王想要在不同的城市间建造一些道路，使得这些城市两两可达。同时，国王不会在同样的两个城市间建造两条或以上的道路。

对于每一种道路的建造方案，国王发现如果这个方案一共建造了$\red{k}$条道路，那么就要花费$\red{k^2}$的钱。

作为一个喜欢思考计数问题的人，国王想要知道所有方案的花费的和是多少呢。

当然结果可能很大，输出答案对于给定的一个数$\red{M}$取模就可以了。

输入格式

一行两个数$\red{n}$和$\red{M，}$分别表示城市的个数和取模的大小。

输出格式

一行表示答案。

样例

输入样例1

7 1000000000

输出样例1

228115272

输入样例2

6 1000000000

输出样例2

1789860

输入样例3

5 1000000000

输出样例3

24600

提示

对于所有的数据，满足:$\red{1<=n<=2000}$。$\red{1<=M<=10^9}$

对于$\red{20\%}$的数据，$\red{n<=8.}$

对于$\red{50\%}$的数据，$\red{n<=50}$。