分数: 1500 点
问题陈述
给你一个整数 N 和素数 P.
我们称一系列 N 间隔 ([L_1,R_1] ,[L_2,R_2], \cdots, [L_N,R_N]) 好 当且仅当满足以下两个条件时:
- 1\le L_i\le R_i\le N 适用于所有 1\le i\le N.
- 存在一个 独特 排列 x=(x_1,x_2,\cdots,x_N) of (1,2,\cdots,N) 这样 L_i\le x_i\le R_i 适用于所有 1\le i\le N.
计算数量,取模 P,属于 好 间隔序列。
约束
- 2 \leq N \leq 5000
- 10^9<P<1.01\times 10^9
- P 是素数。
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N P
输出
打印答案。
示例输入 1
2 1005488041
示例输出 1
6
以下 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])
示例输入 2
5 1005488041
示例输出 2
102960
示例输入 3
100 1005488041
示例输出 3
47599495
示例输入 4
1000 1005488041
示例输出 4
632708165