#P9552. 题目赋分

    ID: 6139 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 7 上传者: 标签>CF2300提高+/省选-差分转化双射计数完全背包计数 DP滚动数组

题目赋分

题面翻译

现在的高考有些科目是赋分制的,你现在在命一套题,赋分规则如下:

  • 有 nn 道还未赋分的题目,你需要给这 nn 道题目赋分。
  • 设第 ii 道题目的分数为 AiA_i。给题目赋分的方案需要满足:
    • 对于任意 i∈[2,n]i \in [2, n],Ai−1≤AiA_{i-1} \leq A_{i}。
    • 对于任意 i∈[1,n]i \in [1, n],1≤Ai≤n1 \leq A_{i} \leq n。
    • 对于任意一个大小为 kk(1≤k<n1 \leq k < n)的题目子集 SS 和任意一个大小为 k+1k+1 的题目子集 TT,需要满足:∑x∈SAx<∑x∈TAx\sum_{x \in S}A_x < \sum_{x\in T}A_x。
  • 你需要计算,有多少种给题目赋分的方案,使得能满足上述三个条件。请求出答案对 MM 取模的结果。

输入格式

一行给出N,M

输出格式

如题

样例 #1

样例输入 #1

2 998244353

样例输出 #1

3

样例 #2

样例输入 #2

3 998244353

样例输出 #2

7

样例 #3

样例输入 #3

6 966666661

样例输出 #3

66

样例 #4

样例输入 #4

96 925309799

样例输出 #4

83779

提示

制約

  • 2 ≤ N ≤ 5000 2\ \leq\ N\ \leq\ 5000
  • 9 × 108 < M < 109 9\ \times\ 10^8\ <\ M\ <\ 10^9