A. Easy Diameter Problem
time limit per test
2.5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Randias is given a tree with $$$n$$$ vertices. He does the following operation until the tree contains $$$0$$$ vertices:

  • choose a vertex which is an endpoint of any diameter, and then remove it.

He asks you to find the number of removal orders modulo $$$10^9+7$$$.

Note that two orders are considered different if and only if there exists $$$i$$$ ($$$1\le i\le n$$$), where the $$$i$$$-th vertex being removed in one order is different from the $$$i$$$-th vertex being removed in the other order.

Recall that a vertex $$$u$$$ is an endpoint of some diameter if there exists a vertex $$$v$$$ such that $$$\texttt{dis}(u,v)\ge \texttt{dis}(i,j)$$$ for any pair of vertices $$$i$$$ and $$$j$$$, where $$$\texttt{dis}(x,y)$$$ represents the number of edges in the shortest path from $$$x$$$ to $$$y$$$.

Input

The first line contains one integer $$$n$$$ ($$$1\le n \le 300$$$), denoting the number of vertices of the tree.

The following $$$n-1$$$ lines, each line contains two integers $$$u$$$ and $$$v$$$ ($$$1\le u,v\le n$$$, $$$u\ne v$$$), denoting an edge connecting $$$u$$$ and $$$v$$$.

It is guaranteed that the edges form a tree.

Output

Print a single integer, denoting the number of removal orders modulo $$$10^9 + 7$$$.

Examples
Input
3
1 2
3 2
Output
4
Input
5
4 1
4 5
1 2
1 3
Output
28
Input
7
5 7
2 5
2 1
1 6
3 6
4 1
Output
116
Note

For the first example, $$$[1,2,3]$$$, $$$[1,3,2]$$$, $$$[3,1,2]$$$, $$$[3,2,1]$$$ are possible removal orders.