/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 1000 点
問題文
正整数 N と素数 P が与えられます．
すべての要素が 0 である長さ N の数列 A=(A_1,A_2,\ldots,A_N) があります．
あなたは以下の操作を 0 回以上好きな回数繰り返すことができます．
- 整数の組 (l, r)\ (1\leq l\leq r\leq N) を選ぶ．A_l,A_{l+1},\ldots,A_r を全て \dfrac{r(r-1)}{2}+l で置き換える．
操作を繰り返すことで最終的に得られる A としてあり得るものの個数を P で割った余りを求めてください．
制約
- 1\leq N\leq 5000
- P は 10^8\lt P\lt 10^9 を満たす素数
- 入力される数値は全て整数
入力
入力は以下の形式で標準入力から与えられる．
N P
出力
答えを出力せよ．
入力例 1
1 998244353
出力例 1
2
得られる A は (0),(1) の 2 通りです．
入力例 2
2 998244353
出力例 2
7
得られる A は (0,0),(0,3),(1,0),(1,2),(1,3),(2,2),(2,3) の 7 通りです．
入力例 3
3 998244353
出力例 3
38
入力例 4
4 998244353
出力例 4
282
入力例 5
77 777777773
出力例 5
112061248
Score : 1000 points
Problem Statement
You are given a positive integer N and a prime P.
There is a sequence A=(A_1,A_2,\ldots,A_N) of length N where all elements are 0.
You can repeat the following operation zero or more times.
- Choose a pair of integers (l, r)\ (1\leq l\leq r\leq N). Replace each of A_l,A_{l+1},\ldots,A_r with \dfrac{r(r-1)}{2}+l.
Find the number, modulo P, of sequences that can be obtained as A after performing operations.
Constraints
- 1\leq N\leq 5000
- P is a prime satisfying 10^8\lt P\lt 10^9.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N P
Output
Output the answer.
Sample Input 1
1 998244353
Sample Output 1
2
The two possible sequences A are (0) and (1).
Sample Input 2
2 998244353
Sample Output 2
7
The seven possible sequences A are (0,0),(0,3),(1,0),(1,2),(1,3),(2,2),(2,3).
Sample Input 3
3 998244353
Sample Output 3
38
Sample Input 4
4 998244353
Sample Output 4
282
Sample Input 5
77 777777773
Sample Output 5
112061248