题目描述

定义 $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

输入

2 1005488041

输出

6

样例 2

输入

5 1005488041

输出

102960

样例 3

输入

100 1005488041

输出

47599495

样例 4

输入

1000 1005488041

输出

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])$