D - Unique Matching 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 1500 点

問題文

整数 N と素数 P が与えられます。

以下がともに満たされるとき、またそのときに限り N 個の区間からなる列 ([L_1,R_1] ,[L_2,R_2], \cdots, [L_N,R_N]) を 良い と呼びます。

  • すべての 1\le i\le N に対して 1\le L_i\le R_i\le N が成り立つ。
  • すべての 1\le i\le N に対して L_i\le x_i\le R_i が成り立つような (1,2,\cdots,N) の順列 x=(x_1,x_2,\cdots,x_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

Score : 1500 points

Problem Statement

You are given an integer N and prime P.

We call a sequence of N intervals ([L_1,R_1] ,[L_2,R_2], \cdots, [L_N,R_N]) good if and only if both of the followings are satisfied:

  • 1\le L_i\le R_i\le N holds for all 1\le i\le N.
  • There exists a unique permutation x=(x_1,x_2,\cdots,x_N) of (1,2,\cdots,N) such that L_i\le x_i\le R_i holds for all 1\le i\le N.

Count the number, modulo P, of good sequences of intervals.

Constraints

  • 2 \leq N \leq 5000
  • 10^9<P<1.01\times 10^9
  • P is prime.
  • All input values are integers.

Input

Input is given from Standard Input in the following format:

N P

Output

Print the answer.

Sample Input 1

2 1005488041

Sample Output 1

6

The following 6 sequences are good:

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

Sample Input 2

5 1005488041

Sample Output 2

102960

Sample Input 3

100 1005488041

Sample Output 3

47599495

Sample Input 4

1000 1005488041

Sample Output 4

632708165