3622: 道路
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：0
解决：
题目描述
某国有n个不同的城市，但一条道路也没有，交流非常的不方便。所以国王想要在不同的城市间建造一些道路，使得这些城市两两可达。同时，国王不会再同样的两个城市间建造两条或以上的道路。
对于每一种道路的建造方案，国王发现如果这个方案一共建造了k条道路，那么就要花费k^2的钱。作为一个喜欢思考计数问题的人，国王想要知道所有方案的花费的和是多少呢。
当然结果可能很大，输出答案对于给定的一个数M取模就可以了。
输入
仅一行两个数n和M，分别表示城市个数和取模大小。
输出
仅一行表示答案。
样例输入 复制
5 1000000000样例输出 复制
24600提示
样例1
Input：5 1000000000
Output：24600
样例2
Input：6 1000000000
Output：1789860
数据范围：
20%的数据：n<=8
50%的数据：n<=50
100%的数据：1<=n>=200,1<=M<=10^9