题目背景

原题链接：https://oier.team/problems/J15C。

---

允许一切的发生。

题目描述

你的人生是一张包含 $n$ 个节点的简单（无重边，无自环）无向图，点的编号为 $0 \sim n-1$，$0$ 号节点是你的起点，边的边权均为 $1$。

你会给你人生中的每一个节点，都找到一条从起点到它的最短路，并选中这条路上的所有边。

你会选中尽量少的边。可以证明，你最终会选中 $n-1$ 条边，且这 $n-1$ 条边会构成一棵树。

这好像是 OIer 的宿命——或是贪心或是动态规划，找到最优路径和最优解，如机器般精确地走下去。

可是，你不是机器啊，你是人啊。你想知道，人生这张图，在已知选中的 $n-1$ 条边的情况下，有多少种可能？可能性也许太多了，你需要对 $10^9+7$ 取模。

当你意识到人生还有这么多可能时，你也许就能与自我和解，不再内耗和焦虑了。

叉叉就是这么做的，他希望祝福大家。

输入格式

一行一个整数 $n$。

接下来 $n-1$ 行，每行两个整数 $x,y$，表示一条选中的边。

输出格式

一行一个整数，表示答案对 $10^9+7$ 取模后的值。

3
0 1
0 2

2

3
0 1
1 2

1

5
0 1
0 2
1 3
1 4

16

提示

【样例解释 #1】

两种可能分别为：

0 1
0 2

和

0 1
0 2
1 2

其中每行表示人生这张图中的一条边。

【数据范围】

对于 $100\%$ 的数据，$2 \le n \le 10^6$，输入的边构成一棵树。

测试点编号	$n =$	特殊性质
$1$	$2$
$2 \sim 3$	$3$
$4 \sim 7$	$4$
$8 \sim 16$	$5$
$17$	$10^6$	$y=x+1$
$18$		$x=0$
$19\sim 21$	$10^3$
$22\sim 25$	$10^6$