← 返回题目列表

AtCoder · agc069_d

D. 树和区间

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

分数: 1200 点

问题陈述

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

对于一棵树 N 顶点标记 1 通过 N,让 a_i 和 b_i 是端点 i第边缘 (1 \leq i \leq N-1)。另外,定义 x_j\ (1 \leq j \leq N-1) 为:

  • 整数个数 i\ (1 \leq i \leq N-1) 满意 \min(a_i,b_i) \leq j \lt \max(a_i,b_i).

求模数 P,可能是 (x_1, x_2, \ldots, x_{N - 1}).

约束

  • 2 \leq N \leq 500
  • 10^8 \leq P \leq 10^9
  • P 是质数。

输入

输入由标准输入按以下格式给出:

N P

输出

打印答案。


示例输入 1

3 998244353

示例输出 1

3

如果我们通过标签而不是边来区分顶点,则存在具有三个顶点的三棵不同的树。
对应 (x_1, x_2) 是 (1, 1), (2, 1),和 (1, 2),所以预期输出是 3 模数 P = 998244353.


示例输入 2

69 433416647

示例输出 2

243082757

求计数模数 P.