Enumeration of Road Network Plans

Memory limit: 64 MB

Byteman is going for a car trip around Byteland, but he is unfortunately unable to buy a map of the country. His friends told him about some properties of the bytean road network:

• There are  cities in Byteland, numbered from  to .
• Each road is bidirectional and connects two different cities.
• Each pair of different cities is connected by exactly one path, consisting of one or more roads, on which no city appears more than once.
• The longest path, on which no city appears more than once, consists of  roads.

Using information that he managed to collect, Byteman is going to try to reconstruct the road map of Byteland. Byteman would not like to work on it too much, so he would like to know the number of different road network plans satisfying the given conditions. During comparison of plans Byteman does not take exact locations of cities into consideration, but only the plan of connections; moreover, he is not interested in particular city numbers. In other words, Byteman considers two plans the same if and only if there exists a one-to-one mapping from cities of one plan to the cities of the other one, such that if cities  and  are connected by a road on the first plan then their equivalents and  are also connected by a road on the second plan.

Task

Write a program that:

• reads numbers ,  and  from the standard input,
• computes the number of different road network plans, that are consistent with information that Byteman managed to collect, modulo ,
• writes the result to the standard output.

Input

The first and only line of the input contains three integers ,  and  (, , ,  is a prime number), separated with single spaces.

Output

The first and only line of output should contain a single integer - the remainder of the division by  of the number of different plans that are consistent with conditions known to Byteman.

Example

For the input data:

6 3 13

the correct result is:

2

Task author: Jakub Radoszewski.

参考了

acm.sjtu.edu.cn/ppca/w/images/5/58/Graphical_enumeration_-_魏祯.pdf

和

http://www.researchgate.net/publication/224105126_The_Enumeration_of_Trees_by_Height_and_Diameter

公式还打错搞了半天。。

然后还把n^3logn优化到n^3才过