← 返回题目列表

AtCoder · agc077_d

D. 范围替换 2

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

分数: 1000 点

问题陈述

给你一个正整数 N 和素数 P.

有一个序列 A=(A_1,A_2,\ldots,A_N) 长度 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.

求模数 P,可以通过以下方式获得的序列 A 执行操作后。

约束

  • 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 998244353

示例输出 2

7

七种可能的序列 A 是 (0,0),(0,3),(1,0),(1,2),(1,3),(2,2),(2,3).


示例输入 3

3 998244353

示例输出 3

38

示例输入 4

4 998244353

示例输出 4

282

示例输入 5

77 777777773

示例输出 5

112061248