[POI 2021/2022 R1] Układanie kart
题目背景
译自 [XXIX Olimpiada Informatyczna – I etap](https://sio2.mimuw.edu.pl/c/oi29-1/dashboard/) [Układanie kart](https://sio2.mimuw.edu.pl/c/oi29-1/p/ukl/)。
题目描述
我们用以下方法将一个排列递增排序:
一次操作：记第一个数字为 $k$，在排列中找到 $k-1$（$k=1$ 则取 $n$），把 $k-1$ 拉到排列的第一个位置，中间的数字依次后移。
一次操作的价值：$k-1$（或 $n$）在原排列的位置（这个从 $0$ 开始标号）。
一个排列的价值：进行若干次操作直到排列有序，价值为每次操作的价值之和。
给你 $n,m$，求所有 $n!$ 个排列的价值之和，对 $m$ 取模。
输入输出格式
输入格式
一行两个正整数，$n,m$。
输出格式
一行一个整数，答案对 $m$ 取模的结果。
输入输出样例
输入样例 #1
2 100
输出样例 #1
1
输入样例 #2
3 100
输出样例 #2
15
输入样例 #3
10 1000
输出样例 #3
100
输入样例 #4
500 100000
输出样例 #4
60000
输入样例 #5
100000 1000
输出样例 #5
0
说明
对于所有数据，$2\leq n\leq 1000000$，$2\leq m\leq 10^9$。
| 子任务编号 | 附加限制 | 分数 |
| :----------: | :----------: | :----------: |
| 1 | $n\leq 10$ | 10 |
| 2 | $n\leq 2000$ | 60 |
| 3 | | 30 |