AT_agc069_d [AGC069D] Tree and Intervals

题目描述

给出两个整数 $N$ 和素数 $P$。

我们有一棵由 $N$ 个节点组成的树，节点的编号从 $1$ 到 $N$。树有 $N-1$ 条边，每条边连接两个节点，记为 $a_i$ 和 $b_i\ (1 \leq i \leq N-1)$。接下来，我们定义 $x_j\ (1 \leq j \leq N-1)$ 为：

• 满足 $\min(a_i, b_i) \leq j < \max(a_i, b_i)$ 的边数，个数记为 $x_j$。

你的任务是计算可能的 $(x_1, x_2, \ldots, x_{N-1})$ 组合的数量，并输出此数量除以 $P$ 的余数。

输入格式

输入由以下形式给出：

$N$ $P$

输出格式

输出答案，表示所求数量除以 $P$ 的余数。

输入输出样例 #1

输入 #1

3 998244353

输出 #1

3

输入输出样例 #2

输入 #2

69 433416647

输出 #2

243082757

说明/提示

约束

• $2 \leq N \leq 500$
• $10^8 \leq P \leq 10^9$
• $P$ 是素数

示例解释

对于一个包含 $3$ 个节点的树，总共有 $3$ 种不同的构型，不区分边，仅区分节点。每种构型对应的 $(x_1, x_2)$ 分别为 $(1, 1), (2, 1), (1, 2)$。因此，输出的结果应该是 $3$ 对 $P=998244353$ 取模的余数。

请计算上述结果并输出。

本翻译由 AI 自动生成