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

The input consists of a single line containing three integers $ n $ , $ d $ and $ m $ ( $ 2

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