Ember and Storm's Tree Game

题意翻译

Ember 和 Storm 正在玩游戏。首先，Ember 构造一棵 $n$ 个节点且每个节点度数不超过 $d$ 的带节点编号的树 $T$。 然后，Storm 选择两个不同的节点 $u$ 和 $v$，并写下从 $u$ 到 $v$ 路径上的节点编号，记为序列 $a_1,a_2,\dots,a_k$。 最后，Ember 在序列中选择一个位置 $i(1\le i<k)$，并在以下两个操作选择一个执行： - 翻转 $a_{i+1}\dots a_k$ 并将这一段加上 $a_i$，操作后序列变为 $a_1,\dots,a_i,a_k+a_i,a_{k-1}+a_i,\dots,a_{i+1}+a_i$。 - 取负 $a_{i+1}\dots a_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$ 为翻转或是取负取决于 Ember 的决策。若 Ember 和 Storm 都使用最优策略（若有多种必胜策略，任选一种执行；若必败，也任选一种执行），试统计所有可能的游戏情形的数量，并输出其取模 $m$ 的结果。

题目描述

Ember and Storm play a game. First, Ember picks a labelled tree $ T $ of $ n $ vertices, such that the degree of every vertex is at most $ d $ . Then, Storm picks two distinct vertices $ u $ and $ v $ in this tree and writes down the labels of the vertices in the path from $ u $ to $ v $ in a sequence $ a_{1},a_{2}...\ a_{k} $ . Finally, Ember picks any index $ i $ ( $ 1<=i<k $ ) in the array. Now he performs one of the following two operations exactly once: - flip the subrange $ [i+1,k] $ and add $ a_{i} $ to it. After this, the sequence becomes $ a_{1},...\ a_{i},a_{k}+a_{i},a_{k-1}+a_{i},...\ a_{i+1}+a_{i} $ - negate the subrange $ [i+1,k] $ and add $ a_{i} $ to it. i.e., the array becomes $ a_{1},...\ a_{i},-a_{i+1}+a_{i},-a_{i+2}+a_{i},...-a_{k}+a_{i} $ Ember wins if the array is monotonically increasing or decreasing after this. Otherwise Storm wins. The game can be described by the tuple $ (T,u,v,i,op) $ where $ op $ is «flip» or «negate» depending on the action Ember chose in the last turn. Find the number of tuples that can occur if Ember and Storm play optimally. When they play optimally, if there are multiple moves by which they are guaranteed to win, then they may play any of the winning moves. Otherwise, if someone loses no matter what they play, then they may play any of the possible moves. Report the answer modulo $ m $ .

输入输出格式

输入格式

The input consists of a single line containing three integers $ n $ , $ d $ and $ m $ ( $ 2<=n<=200,1<=d<n,1<=m<=2·10^{9} $ ).

输出格式

Print a single number — the number of possible tuples if Ember and Storm play as described, modulo $ m $ .

输入输出样例

输入样例 #1

2 1 1000000007

输出样例 #1

4

输入样例 #2

3 1 250

输出样例 #2

0

输入样例 #3

3 2 100

输出样例 #3

36

说明

In the first sample case, there is only one possible tree. There are two possible paths, $ 1 $ to $ 2 $ and $ 2 $ to $ 1 $ . For both paths, $ i $ can only be $ 1 $ , and $ op $ can take both possibilities. Therefore, the answer is $ 4 $ . In the second sample, there are no possible trees. In the third sample, there are three possible trees.