CF914H Ember and Storm's Tree Game

Ember 和 Storm 在玩一个游戏。首先，Ember 选择一个有 $n$ 个点的有标号树 $T$，并且每个点的度数都不超过 $d$。接着，Storm 在这棵树上任选两个不同的点 $u$ 和 $v$，把从 $u$ 到 $v$ 的路径上经过的点的标号按顺序写成一个序列 $a_{1},a_{2},\dots,a_{k}$。然后，Ember 在数组中任选一个下标 $i$（$1 \leq i < k$），并且对序列执行以下两个操作之一（且只能执行一次）： - 翻转子区间 $[i+1,k]$ 并将 $a_{i}$ 加到该区间每个元素上。此后，序列变为 $a_{1},\dots,a_{i},a_{k}+a_{i},a_{k-1}+a_{i},\dots,a_{i+1}+a_{i}$。 - 取 $[i+1,k]$ 子区间的相反数，并将 $a_{i}$ 加到该区间每个元素上。即，序列变为 $a_{1},\dots,a_{i},-a_{i+1}+a_{i},-a_{i+2}+a_{i},\dots,-a_{k}+a_{i}$。 如果经过操作后，该数组是单调递增或单调递减的，Ember 获胜。否则，Storm 获胜。 这个游戏可以用一个五元组 $(T,u,v,i,op)$ 来描述，其中 $op$ 为「flip」或「negate」，代表 Ember 最后选择的操作。若 Ember 和 Storm 都足够聪明且最优地行动，问可能出现的五元组个数是多少。如果他们有多种方式可以保证获胜，则可以任选一种方式。否则，如果无论如何都会输，则可以任选一种可行方式。 请输出所有可能的五元组总数，答案对 $m$ 取模。

输入包含一行，包含三个整数 $n$、$d$ 和 $m$，$2 \leq n \leq 200$，$1 \leq d < n$，$1 \leq m \leq 2 \cdot 10^{9}$。

输出一个整数，表示当 Ember 和 Storm 如题中所述地进行游戏时，可能的五元组数量，对 $m$ 取模。

在第一个样例中，只存在一棵可能的树。有两条路径，$1$ 到 $2$ 和 $2$ 到 $1$。对于每条路径，$i$ 只能取 $1$，$op$ 有两种可能。因此答案为 $4$。 在第二个样例中，没有可能的树。 在第三个样例中，有三棵不同的树。 由 ChatGPT 5 翻译