给定一棵 n 个点的有根树,点的标号为 1⋯n ,根的标号为 1。
定义 dis(x) 为点 x 到根的最短路径的边的数量,lca(x,y) 为 x,y 的最近公共祖先。
你需要求有几个 1⋯n 的排列 p ,满足对于 1≤i<n−1,有 dis(lca(pi,pi+1))≤dis(lca(pi+1,pi+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≤ui,vi≤n;ui≠vi。
- 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): 没有额外的限制。