There is a tree with nodes numbered from to . For each , the -th edge connects node and node .
You are going to paint all nodes in distinct colors. Colors are represented by integers between and .
The assignment of colors on the tree is called good, if it is possible to complete the following operation times repeatedly.
Select a pair of colors which satisfies the following two conditions.
.
There exists an edge which connects a node painted in color and a node painted in color .
Change the color of all nodes currently painted in color to color .
Your task is to count the number of good assignments of colors on the tree modulo .
输入格式
The input consists of a single test case of the following format.
The first line consists of an integer , which satisfies . Each of the lines consists of two integers , which satisfies . The given graph is guaranteed to be a tree.
输出格式
Output in a line the number of assignments of colors on the given tree modulo .
