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