In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].

If you are familiar with IRC chat, the support team is also reachable on PIRC network (irc.pirc.pl) in #szkopul channel. If you are not, just use email.

Please do not ask us things like "how to solve task XYZ?".

Please remember that the support team has to sleep sometimes or go to work in real life.

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: