Ember and Storm's Tree Game
Contest: Codecraft-18 and Codeforces Round 458 (Div. 1 + Div. 2, combined)
Difficulty rating: 3400
Tags: combinatorics, dp, games, trees

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 a1, a2... ak. 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 ai to it. After this, the sequence becomes a1, ... ai, ak + ai, ak - 1 + ai, ... ai + 1 + ai
- negate the subrange [i + 1, k] and add ai to it. i.e., the array becomes a1, ... ai,  - ai + 1 + ai,  - ai + 2 + ai, ... - ak + ai

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 format:
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 format:
Print a single number  — the number of possible tuples if Ember and Storm play as described, modulo m.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

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.

Example input:
2 1 1000000007

Example output:
4

Example input:
3 1 250

Example output:
0

Editorial:
Ember wins if the path chosen by Storm is monotonic or bitonic. In this case, there can be two (i, op) pairs.
Let S be the set of trees having n vertices in which all paths are bitonic or monotonic. We need to find 2n(n - 1)|S|.
For every tree in S, there exists at least one vertex such that every path starting or ending at that vertex is monotonically increasing or decreasing.
First, let's count the number of rooted trees such that all paths starting at the root are increasing. Later we'll combine this with trees having decreasing paths.
Let tree[i][deg] be the number of trees having i vertices and maximum degree d such that all paths starting at vertex 1 are monotonically increasing and the degree of the vertex 1 is deg. We can find this quantity by a kind of knapsack DP in $${\mathcal {O}}(n^{3}\log n)$$, as follows.
We can construct a tree of k + i·j vertices and degree of root deg + j by taking a tree of k vertices having root degree deg and attaching j trees of i vertices each to its root. Let the set of vertices be V = {1, ... k + i·j}. Initially we remove k vertices from V and use these vertices to construct the tree of k vertices. Let W be the set of remaining vertices. We partition W into j subsets of i vertices each. Sort these subsets by their minimum element. Now we make j trees of i vertices each, and use the l-th set of vertices to construct the l-th tree. Therefore, the number of ways to do this is:
where tree[i][any] is the number of trees of i vertices with any root degree from 1 to d - 1.
Note that there is a bijection from trees in which all paths from root are increasing and trees in which all paths from root are decreasing. ($$v \mapsto n - v + 1$$)
Note that tree[i + 1][j]·tree[n - i][k] is the number of trees such that all paths starting at the root are monotonic, and there are i vertices lying on the increasing paths and there are n - i - 1 vertices lying on the decreasing paths, and the degree of the root is j + k Therefore the quantity
is the number of rooted trees of n vertices such that all paths starting at the root are monotonically increasing or decreasing. However, we want to count unrooted trees.
Note that if a tree in S has k possible roots, then these roots form a chain of consecutive numbers with an increasing tree of size i on the larger end of the chain and a decreasing tree of size n - k - i on the smaller end of the chain. Such a tree gets counted k times in a. But for all of these roots except one, there is exactly one child of the root smaller than it. Therefore the total number of unrooted trees is
Time Complexity: $${\mathcal {O}}(n^{3}\log n)$$