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。
在第二个示例中,没有可能的树。
在第三个示例中,存在三种可能的树。