← 返回题目列表

AtCoder · agc067_d

D. 独特的匹配

中文机器翻译题面 查看原题

分数: 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