/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 1200 点
問題文
コンテストで使う N 問の問題がジャッジに選ばれ、各問に配点を付ける段階になりました。
問題 i の配点 A_i は、1 以上 N 以下の整数でなければなりません。 また、すでに問題は難易度順に並んでおり、A_1 \le A_2 \le \ldots \le A_N でなければなりません (複数問の配点が同じになるのは構いませんが)。
ICPC のファンであるあなたは、解いた問題数が多い参加者ほど上位となってほしいと考えています。 この理由から、任意の k (1 \le k \le N-1) に対して、任意の k 問の配点の合計が任意の k+1 問の配点の合計より真に小さくなるようにしたい、とあなたは考えています。
このような配点の付け方は何通りあるでしょうか？この数を与えられた素数 M で割った余りを求めてください。
制約
- 2 \leq N \leq 5000
- 9 \times 10^8 < M < 10^9
- M は素数である。
- 入力中のすべての値は整数である。
入力
入力は以下の形式で標準入力から与えられる。
N M
出力
配点の付け方の数を M で割った余りを出力せよ。
入力例 1
2 998244353
出力例 1
3
可能な配点の付け方は (1, 1), (1, 2), (2, 2) です。
入力例 2
3 998244353
出力例 2
7
可能な配点の付け方は (1, 1, 1), (1, 2, 2), (1, 3, 3), (2, 2, 2), (2, 2, 3), (2, 3, 3), (3, 3, 3) です。
入力例 3
6 966666661
出力例 3
66
入力例 4
96 925309799
出力例 4
83779
Score : 1200 points
Problem Statement
N problems have been chosen by the judges, now it's time to assign scores to them!
Problem i must get an integer score A_i between 1 and N, inclusive. The problems have already been sorted by difficulty: A_1 \le A_2 \le \ldots \le A_N must hold. Different problems can have the same score, though.
Being an ICPC fan, you want contestants who solve more problems to be ranked higher. That's why, for any k (1 \le k \le N-1), you want the sum of scores of any k problems to be strictly less than the sum of scores of any k+1 problems.
How many ways to assign scores do you have? Find this number modulo the given prime M.
Constraints
- 2 \leq N \leq 5000
- 9 \times 10^8 < M < 10^9
- M is a prime.
- All input values are integers.
Input
Input is given from Standard Input in the following format:
N M
Output
Print the number of ways to assign scores to the problems, modulo M.
Sample Input 1
2 998244353
Sample Output 1
3
The possible assignments are (1, 1), (1, 2), (2, 2).
Sample Input 2
3 998244353
Sample Output 2
7
The possible assignments are (1, 1, 1), (1, 2, 2), (1, 3, 3), (2, 2, 2), (2, 2, 3), (2, 3, 3), (3, 3, 3).
Sample Input 3
6 966666661
Sample Output 3
66
Sample Input 4
96 925309799
Sample Output 4
83779