As the top scorer in the C City high school entrance examination, Xiao Zhen entered Mianzi Middle School to study for informatics competitions without any suspense.

After joining Mianzi Middle School, he learned many algorithms under the guidance of Senior Wang, one of which was centroid decomposition.

The centroid decomposition Xiao Zhen learned was taught to him by Senior Wang, and it is an algorithm that works as follows:

• Initially, the current connected component is the entire tree.
• First, find any node $u$ in the current connected component to serve as the decomposition center for this step (it does not have to be the centroid).
• Second, remove node $u$ from the current connected component, which results in several smaller connected components. Recursively perform this operation for each of these connected components.

It is not difficult to see that the centroid decomposition Xiao Zhen learned from the black-hearted Senior Wang can reach a recursion depth of $O(n)$ in the worst case. Now, curious Xiao Zhen wants to know, for a given tree with $n$ nodes, how many different centroid decomposition schemes are there? Since the answer may be very large, you only need to output the value modulo $10^9+7$.

Two centroid decomposition schemes are considered different if and only if the chosen decomposition center is different for at least one connected component.

To avoid ambiguity due to different details in the algorithms learned by everyone, we have provided a brute-force code (see show.cpp in the provided files) to specifically describe this algorithm.

Input

The first line contains an integer $n$, representing the number of nodes in the tree.

The next $n-1$ lines each contain two positive integers $x$ and $y$, indicating that there is an edge between node $x$ and node $y$.

Node labels start from $1$.

Output

Output a single integer representing the answer modulo $10^9+7$.

Examples

Input 1

3
1 2
2 3

Output 1

5

Note 1

For Example 1, there are five different centroid decomposition schemes:

1. First layer selects "1", second layer selects "2", third layer selects "3".
2. First layer selects "1", second layer selects "3", third layer selects "2".
3. First layer selects "2", second layer selects "1, 3".
4. First layer selects "3", second layer selects "2", third layer selects "1".
5. First layer selects "3", second layer selects "1", third layer selects "2".

Input 2

10
1 2
1 3
1 4
4 5
1 6
6 7
3 8
5 9
2 10

Output 2

78904

Subtasks

The evaluation uses bundled subtasks. To receive points for a subtask, you must pass all test cases within it.

For all data, $1\le n \le 5000$, and it is guaranteed that the input is a tree.

Subtask 1 [5 pts]: $n\le 10$.

Subtask 2 [10 pts]: The given tree is guaranteed to be a chain.

Subtask 3 [10 pts]: $n\le 20$.

Subtask 4 [25 pts]: $n\le 60$.

Subtask 5 [20 pts]: $n\le 400$.

Subtask 6 [30 pts]: $n\le 5000$.

Note

To avoid ambiguity due to different details in the algorithms learned by everyone, the file show.cpp is provided in the distributed files to specifically describe this algorithm.