给定一棵 $n$ 个点的有根树，点的标号为 $1 \cdots n$ ，根的标号为 $1$。

定义 $\mathrm{dis}(x)$ 为点 $x$ 到根的最短路径的边的数量，$\mathrm{lca}(x,y)$ 为 $x,y$ 的最近公共祖先。

你需要求有几个 $1 \cdots n$ 的排列 $p$ ，满足对于 $1 \leq i < n - 1$，有 $\mathrm{dis}(\mathrm{lca}(p_i,p_{i+1})) \leq \mathrm{dis}(\mathrm{lca}(p_{i+1},p_{i+2}))$。

由于答案可能很大，你只需要输出答案对 $1000000007$ 取模后的值。

输入格式

第一行一个正整数 $n$ 表示点数。

接下来 $n$ 行，每行两个整数 $(x,y)$，表示树的一条边 $(x,y)$。

输出格式

输出方案数对 $1000000007$ 取模后的值

样例数据

样例 1 输入

3
1 2
2 3

样例 1 输出

4

样例 2 输入

5
1 2
2 3
1 4
4 5

样例 2 输出

56

子任务

对于所有的测试点，均满足 $2≤n≤80;1≤u_i,v_i≤n;u_i≠v_i$。

• Subtask 1(9 pts): $n≤8$。
• Subtask 2(11 pts): $n≤15$。
• Subtask 3(15 pts): $n≤30$。
• Subtask 4(25 pts): $n≤50$。
• Subtask 5(40 pts): 没有额外的限制。