Automorphisms [B]

Memory limit: 128 MB

A tree is an undirected graph in which any two nodes are connected with at most one simple path, that is, a path without repeating nodes.

Consider a tree with nodes numbered through . Let be a permutation of the set of nodes of the tree, that is, a one-to-one function (injection) . The permutation is called an automorphism if for any two nodes , of the tree, the nodes and are connected with an edge if and only if and are connected with an edge.

We would like to know what is the number of different automorphisms of a given tree modulo .

Input

The first line of the standard input contains an integer (): the number of nodes of the tree. Each of the following lines contains two integers and () that represent an edge connecting the nodes and .

Output

The first and only line of the standard output should contain one integer: the number of different automorphisms of the given tree modulo .

Example

For the input data:

6
1 3
2 3
3 4
4 5
4 6

the correct result is:

8

Explanation of the example: This tree has 8 automorphisms, in particular, the following three:

• for
• for , ,
• , , , , , .

Task author: Adam Malinowski.