Given a rooted tree with $n$ nodes, labeled $1 \dots n$, where the root is labeled $1$.

Define $\mathrm{dis}(x)$ as the number of edges on the shortest path from node $x$ to the root, and $\mathrm{lca}(x, y)$ as the lowest common ancestor of $x$ and $y$.

You need to find the number of permutations $p$ of $1 \dots n$ such that for all $1 \leq i < n - 1$, the condition $\mathrm{dis}(\mathrm{lca}(p_i, p_{i+1})) \leq \mathrm{dis}(\mathrm{lca}(p_{i+1}, p_{i+2}))$ holds.

Since the answer may be very large, you only need to output the answer modulo $1000000007$.

Input

The first line contains a positive integer $n$ representing the number of nodes.

The next $n-1$ lines each contain two integers $(x, y)$, representing an edge $(x, y)$ in the tree.

Output

Output the number of valid permutations modulo $1000000007$.

Examples

Input 1

3
1 2
2 3

Output 1

4

Input 2

5
1 2
2 3
1 4
4 5

Output 2

56

Subtasks

For all test cases, $2 \leq n \leq 80$ and $1 \leq u_i, v_i \leq n$ with $u_i \neq v_i$.

• Subtask 1 (9 pts): $n \leq 8$.
• Subtask 2 (11 pts): $n \leq 15$.
• Subtask 3 (15 pts): $n \leq 30$.
• Subtask 4 (25 pts): $n \leq 50$.
• Subtask 5 (40 pts): No additional constraints.