CF914H.Ember and Storm's Tree Game

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.

Ember 和 Storm 进行一场游戏。首先，Ember 选择一棵具有 $n$ 个顶点的带标号树 $T$，使得每个顶点的度数至多为 $d$。接着，Storm 在该树中选择两个不同的顶点 $u$ 和 $v$，并将从 $u$ 到 $v$ 的路径上各顶点的标号按顺序记为序列 $a_1,\,a_2,\ldots,a_k$。最后，Ember 在该数组中任选一个下标 $i$（满足 $1 \le i < k$）。此时他恰好执行以下两种操作之一：

• 翻转子区间 $[i+1,\,k]$ 并将 $a_i$ 加到其中每个元素上。操作后，序列变为
  $a_1,\,\ldots,\,a_i,\,a_k + a_i,\,a_{k-1} + a_i,\,\ldots,\,a_{i+1} + a_i$；
• 取负子区间 $[i+1,\,k]$ 并将 $a_i$ 加到其中每个元素上，即序列变为
  $a_1,\,\ldots,\,a_i,\,-a_{i+1} + a_i,\,-a_{i+2} + a_i,\,\ldots,\,-a_k + a_i$。

若执行操作后该数组单调递增或单调递减，则 Ember 获胜；否则 Storm 获胜。

该游戏可用五元组 $(T,\,u,\,v,\,i,\,\text{op})$ 描述，其中 $\text{op}$ 为 “flip” 或 “negate”，取决于 Ember 在最后一轮所选择的操作。求在双方均以最优策略进行游戏时，可能产生的不同五元组的总数。所谓“最优策略”是指：若存在多种操作可确保获胜，则玩家可任选其一；若无论采取何种操作均必败，则玩家可在所有合法操作中任选其一。

请输出答案对 $m$ 取模的结果。

The input consists of a single line containing three integers n, d and m (2 ≤ n ≤ 200, 1 ≤ d < n, 1 ≤ m ≤ 2·109).

输入包含一行，其中为三个整数 $n$、$d$ 和 $m$（满足 $2 \leq n \leq 200$，$1 \leq d < n$，$1 \leq m \leq 2\cdot10^9$）。

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

输出一个数字——即 Ember 和 Storm 按照上述方式游戏时可能的元组数量，对 $m$ 取模。

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.

在第一个样例中，只存在一种可能的树。共有两条可能的路径：1 到 2，以及 2 到 1。对于这两条路径，i 只能取 1，而 op 可以取两种可能的值。因此，答案为 4。

在第二个样例中，不存在任何可能的树。

在第三个样例中，存在三种可能的树。