← 返回题目列表

Codeforces · 914/H

H. 余烬和风暴之树游戏

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

Ember 和 Storm 玩游戏。首先,Ember 选择一棵有 n 个顶点的标记树 T,使得每个顶点的度数最多为 d。然后,Storm 在这棵树中选取两个不同的顶点 u 和 v,并按照 a1、a2...ak 的顺序记下从 u 到 v 的路径中的顶点标签。最后,Ember 选择数组中的任意索引 i (1 ≤ i < k)。现在他只执行一次以下两个操作之一:

- 翻转子范围 [i + 1, k] 并向其添加 ai。此后,序列变为 a1, ... ai, ak + ai, ak - 1 + ai, ... ai + 1 + ai
- 否定子范围 [i + 1, k] 并向其添加 ai。即数组变为 a1, ... ai,  - ai + 1 + ai,  - ai + 2 + ai, ... - ak + ai

如果数组在此之后单调递增或递减,则 Ember 获胜。否则风暴获胜。

游戏可以用元组 (T, u, v, i, op) 来描述,其中 op 是“翻转”或“否定”,具体取决于 Ember 在上一回合中选择的动作。求 Ember 和 Storm 发挥最佳性能时可能出现的元组数量。当他们发挥最佳时,如果有多个动作可以保证他们获胜,那么他们可以使用任何获胜的动作。否则,如果有人无论怎么下都输了,那么他们可能会下任何可能的棋步。

报告以 m 为模的答案。

输入

输入由一行组成,其中包含三个整数 n、d 和 m (2 ≤ n ≤ 200、1 ≤ d < n、1 ≤ m ≤ 2·109)。

输出

打印一个数字——如果 Ember 和 Storm 按照描述的方式玩,可能的元组数量,以 m 为模。

示例

输入 #1

2 1 1000000007

输出 #1

4

输入 #2

3 1 250

输出 #2

0

输入 #3

3 2 100

输出 #3

36

注意

在第一个示例中,只有一棵可能的树。有两种可能的路径,1到2和2到1。对于这两种路径,i只能为1,op可以采取两种可能。因此,答案是4。

在第二个示例中,没有可能的树。

在第三个示例中,存在三种可能的树。