题目描述

我们用以下方法将一个排列递增排序:

一次操作：记第一个数字为 $k$，在排列中找到 $k-1$（$k=1$ 则取 $n$），把 $k-1$ 拉到排列的第一个位置，中间的数字依次后移。

一次操作的价值：$k-1$（或 $n$）在原排列的位置（这个从 $0$ 开始标号）。

一个排列的价值：进行若干次操作直到排列有序，价值为每次操作的价值之和。

给你 $n,m$，求所有 $n!$ 个排列的价值之和，对 $m$ 取模。

输入格式

一行两个正整数，$n,m$。

输出格式

一行一个整数，答案对 $m$ 取模的结果。

输入输出样例 #1

输入 #1

2 100

输出 #1

1

输入输出样例 #2

输入 #2

3 100

输出 #2

15

输入输出样例 #3

输入 #3

10 1000

输出 #3

100

输入输出样例 #4

输入 #4

500 100000

输出 #4

60000

输入输出样例 #5

输入 #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