题目描述

定义 $n$ 个区间是好的，当且仅当：

• $1 \leq l_i \leq r_i \leq N$。
• 存在唯一的 $N$ 阶排列 $x_1,x_2,\cdots,x_N$，使得 $x_i \in \left[ l_i , r_i\right]$

给定整数 $N$、素数 $P$。

求有多少组 $\left[l_1,r_1\right],\left[l_2,r_2\right],\cdots,\left[l_N,r_N\right]$ 是好的。

答案对 $P$ 取模。

输入格式

一行用空格隔开的两个整数 $N,P$。

输出格式

一行一个整数，答案。

输入输出样例 #1

输入 #1

2 1005488041

输出 #1

6

输入输出样例 #2

输入 #2

5 1005488041

输出 #2

102960

输入输出样例 #3

输入 #3

100 1005488041

输出 #3

47599495

输入输出样例 #4

输入 #4

1000 1005488041

输出 #4

632708165

说明/提示

• $2 \leq N \leq 5000$
• $10^9 < P <1.01 \times 10^9$
• $P$ 为素数
• 所有输入值均为整数

样例解释 #1

以下为 $6$ 个好的排列：

• $([1,1],[2,2])$
• $([1,2],[2,2])$
• $([1,1],[1,2])$
• $([2,2],[1,1])$
• $([2,2],[1,2])$
• $([1,2],[1,1])$