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_.
## Input
The input consists of a single line containing three integers _n_, _d_ and _m_ (2 ≤ _n_ ≤ 200, 1 ≤ _d_ < _n_, 1 ≤ _m_ ≤ 2·109).
## Output
Print a single number — the number of possible tuples if Ember and Storm play as described, modulo _m_.
[samples]
## Note
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.
[{"iden":"statement","content":"Ember 和 Storm 玩一个游戏。首先，Ember 选择一个包含 #cf_span[n] 个顶点的带标签树 #cf_span[T]，使得每个顶点的度数至多为 #cf_span[d]。然后，Storm 在这棵树中选择两个不同的顶点 #cf_span[u] 和 #cf_span[v]，并写下从 #cf_span[u] 到 #cf_span[v] 的路径上顶点的标签，形成一个序列 #cf_span[a1, a2... ak]。最后，Ember 在数组中选择任意一个索引 #cf_span[i]（#cf_span[1 ≤ i < k]），并恰好执行以下两种操作之一：\n\nEmber 获胜当且仅当操作后数组单调递增或单调递减；否则 Storm 获胜。\n\n该游戏可以用元组 #cf_span[(T, u, v, i, op)] 描述，其中 #cf_span[op] 为 «flip» 或 «negate»，取决于 Ember 在最后一轮选择的操作。求当 Ember 和 Storm 均采取最优策略时，可能出现的元组数量。当他们采取最优策略时，如果存在多个能保证他们获胜的走法，他们可以任选其一；否则，如果无论怎么走都会输，他们也可以任选任意可能的走法。\n\n请输出答案对 #cf_span[m] 取模的结果。\n\n输入包含一行，包含三个整数 #cf_span[n], #cf_span[d] 和 #cf_span[m]（#cf_span[2 ≤ n ≤ 200, 1 ≤ d < n, 1 ≤ m ≤ 2·109]）。\n\n输出一个数 —— 当 Ember 和 Storm 按上述规则玩时，可能的元组数量，对 #cf_span[m] 取模。\n\n在第一个样例中，只有一种可能的树。有两种可能的路径：从 #cf_span[1] 到 #cf_span[2] 和从 #cf_span[2] 到 #cf_span[1]。对于这两条路径，#cf_span[i] 只能是 #cf_span[1]，而 #cf_span[op] 可以取两种可能。因此答案是 #cf_span[4]。\n\n在第二个样例中，不存在可能的树。\n\n在第三个样例中，存在三种可能的树。 "},{"iden":"input","content":"The input consists of a single line containing three integers #cf_span[n], #cf_span[d] and #cf_span[m] (#cf_span[2 ≤ n ≤ 200, 1 ≤ d < n, 1 ≤ m ≤ 2·109])."},{"iden":"output","content":"Print a single number — the number of possible tuples if Ember and Storm play as described, modulo #cf_span[m]."},{"iden":"examples","content":"Input2 1 1000000007Output4Input3 1 250Output0Input3 2 100Output36"},{"iden":"note","content":"In the first sample case, there is only one possible tree. There are two possible paths, #cf_span[1] to #cf_span[2] and #cf_span[2] to #cf_span[1]. For both paths, #cf_span[i] can only be #cf_span[1], and #cf_span[op] can take both possibilities. Therefore, the answer is #cf_span[4].In the second sample, there are no possible trees.In the third sample, there are three possible trees. "}]}
Let $ \mathcal{T}_{n,d} $ denote the set of all labeled trees on $ n $ vertices with maximum degree at most $ d $.
For each tree $ T \in \mathcal{T}_{n,d} $, let $ \mathcal{P}(T) $ denote the set of all simple paths in $ T $, represented as ordered sequences of vertex labels. Since paths are undirected, each unordered pair $ \{u,v\} $ with $ u \ne v $ corresponds to two directed paths: one from $ u $ to $ v $, and one from $ v $ to $ u $. Thus, $ |\mathcal{P}(T)| = 2 \cdot \binom{n}{2} = n(n-1) $, but only if all pairs are connected by a unique path (which they are in a tree).
For each path $ p = (a_1, a_2, \dots, a_k) \in \mathcal{P}(T) $, let $ I(p) = \{1, 2, \dots, k-1\} $ be the set of valid indices $ i $ where Ember can act (i.e., $ 1 \le i < k $).
For each such $ (T, p, i) $, Ember may perform one of two operations:
- **Flip**: Reverse the subarray $ (a_1, \dots, a_i) $, leaving $ (a_{i+1}, \dots, a_k) $ unchanged.
- **Negate**: Multiply each element in the entire array $ (a_1, \dots, a_k) $ by $ -1 $.
After the operation, the resulting array is monotonically increasing or decreasing if and only if it is sorted in non-decreasing or non-increasing order.
Define the set of winning tuples:
$$
\mathcal{W} = \left\{ (T, u, v, i, \text{op}) \mid T \in \mathcal{T}_{n,d},\, \{u,v\} \subset V(T),\, u \ne v,\, i \in I(p_{u,v}),\, \text{op} \in \{\text{flip}, \text{negate}\},\, \text{result is monotonic} \right\}
$$
But since both players play **optimally**, we must consider the game-theoretic structure:
- **Ember** chooses $ T \in \mathcal{T}_{n,d} $ first.
- **Storm** then chooses $ (u,v) $ to try to make it hard for Ember to win.
- **Ember** then chooses $ i $ and $ \text{op} $ to try to make the array monotonic.
Ember **wins** if, **for the chosen $ T $**, **for every possible $ (u,v) $** chosen by Storm, **there exists at least one** $ i \in I(p_{u,v}) $ and one $ \text{op} \in \{\text{flip}, \text{negate}\} $ such that the result is monotonic.
But the problem says:
> *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.*
This implies:
We are to count **all tuples** $ (T, u, v, i, \text{op}) $ that **can occur** under optimal play.
That is:
- Ember chooses a tree $ T $ such that **for every** $ (u,v) $, **there exists** at least one $ (i, \text{op}) $ making the result monotonic. (Otherwise, if for some $ (u,v) $, no $ (i, \text{op}) $ works, then Storm can choose that path and Ember loses — so Ember will not choose such a $ T $.)
- Storm, knowing $ T $, may choose **any** $ (u,v) $ — but since Ember must win **no matter what** Storm does, Ember only chooses trees $ T $ that are **winning** (i.e., for all $ (u,v) $, at least one $ (i, \text{op}) $ leads to monotonicity).
- Then, for each such winning $ T $, Storm picks **any** $ (u,v) $ (since Storm plays optimally to prevent Ember from winning, but if Ember has a winning strategy, Storm cannot prevent it — so Storm picks arbitrarily among all $ (u,v) $).
- Then Ember picks **any** $ (i, \text{op}) $ that makes the array monotonic (since multiple winning moves exist, any can be chosen).
Thus, the set of possible tuples is:
$$
\bigcup_{T \in \mathcal{W}_{\text{win}}} \left( \{T\} \times \mathcal{P}(T) \times \bigcup_{p \in \mathcal{P}(T)} \left( \{ i \in I(p) \mid \text{flip or negate at } i \text{ makes } p \text{ monotonic} \} \times \{\text{flip}, \text{negate}\} \right) \right)
$$
But since for each $ T \in \mathcal{W}_{\text{win}} $, and for **each** path $ p \in \mathcal{P}(T) $, **at least one** $ (i, \text{op}) $ works, and Ember may choose **any** such winning $ (i, \text{op}) $, then for each $ (T, p) $, we count **all** $ (i, \text{op}) $ such that applying $ \text{op} $ at index $ i $ yields a monotonic sequence.
Therefore, the total number of tuples is:
$$
\sum_{T \in \mathcal{T}_{n,d}^{\text{win}}} \sum_{p \in \mathcal{P}(T)} \left| \left\{ (i, \text{op}) \in I(p) \times \{\text{flip}, \text{negate}\} \mid \text{op applied at } i \text{ makes } p \text{ monotonic} \right\} \right|
$$
where $ \mathcal{T}_{n,d}^{\text{win}} = \left\{ T \in \mathcal{T}_{n,d} \mid \forall p \in \mathcal{P}(T),\, \exists (i, \text{op}) \text{ s.t. result is monotonic} \right\} $
But note: the problem says **"if there are multiple moves by which they are guaranteed to win, then they may play any of the winning moves"** — meaning that for a fixed $ T $, if for a given $ p $, multiple $ (i, \text{op}) $ lead to win, then **all** such $ (i, \text{op}) $ are **possible** outcomes under optimal play.
Therefore, the answer is:
$$
\boxed{
\sum_{\substack{T \in \mathcal{T}_{n,d} \\ \forall (u,v) \in V(T)^2,\, u \ne v,\, \exists i \in I(p_{u,v}),\, \exists \text{op} \in \{\text{flip}, \text{negate}\} \\ \text{such that the result is monotonic}}}
\sum_{\substack{(u,v) \in V(T)^2 \\ u \ne v}}
\sum_{\substack{i=1 \\ i < |p_{u,v}|}}^{ |p_{u,v}|-1 }
\sum_{\text{op} \in \{\text{flip}, \text{negate}\}}
\mathbf{1}\left[ \text{op applied at } i \text{ to } p_{u,v} \text{ yields monotonic array} \right]
}
$$
This is the formal mathematical expression of the problem.