Problem Description

Given an integer $ N $ and a prime number $ P $.

A sequence of $ N $ intervals $([L_1,R_1]\ ,[L_2,R_2],\ \cdots,\ [L_N,R_N])$ is called good if and only if both of the following conditions are satisfied:

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

Find the number of good sequences of intervals modulo $ P $.

Input Format

The input is given from the standard input in the following format:

$ N $ $ P $

Output Format

Output the answer.

Sample Input and Output

Sample Input #1

2 1005488041

Sample Output #1

6

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

Notes/Hints

Constraints

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

Sample Explanation 1

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

见题面 Input 部分

见题面 Output 部分