给定一棵 $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): 没有额外的限制。