← 返回题目列表

AtCoder · agc041_d

D. 问题分数

中文机器翻译题面 查看原题

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