题目描述

有份 dfs 的代码：

void dfs(int u) {
    vis[u] = true;
    for (int v = 1; v <= n; v++)
        if (g[u][v] == true && vis[v] == false)
            dfs(v), link(u, v);
}

这个代码表示对一个点数为 $n$ 的无向连通图进行遍历。

其中 $g[u][v]$ 是一个布尔数组，如果图有边 $(u,v)$ 则 $g[u][v] = g[v][u] = \text{true}$，否则 $g[u][v] = g[v][u] = \text{false}$。特别地，对于任意的 $1 \leq u \leq n$ 都有 $g[u][u] = \text{false}$。

$\text{link}(x,y)$ 表示在另一个点数为 $n$ 的图 $T$ 上连边 $(x,y)$。注意，初始时 $T$ 中只有 $n$ 个点而没有任何边。容易得到，执行 $\text{dfs}(1)$ 之后 $T$ 将会是一棵树。

求对于给定的树 $T$，有多少个没有重边和自环的无向连通图 $G$ 满足对 $G$ 执行 $\text{dfs}(1)$ 之后得到的树 $T$ 与给定的树完全一样？

两个图完全一样，当且仅当这两个图的节点数相同并且对于第一个图的任意一条边 $(u,v)$，第二个图中都有边 $(u,v)$ 存在。

输入格式

在文件 dfs.in 中读入。

第一行一个正整数 $n$，表示树 $T$ 的点数，也是无向连通图的点数。

接下来的 $n - 1$ 行，每行两个正整数 $u,v$，表示树 $T$ 上有边 $(u,v)$。

输出格式

在文件 dfs.out 中输出。

输出一个整数表示答案。由于答案可能很大，你只要输出其对 $10^9 + 7$ 取模后的结果。

样例

样例输入 #1

5
1 2
1 3
2 4
2 5

样例输出 #1

4

样例 1 解释

下面这张图是一个合法的图 $G$，加粗的边即为执行了 dfs(1) 后得到的树 $T$：

样例输入 #2

8
1 2
1 3
2 4
2 5
1 7
6 7
8 6

样例输出 #2

16

大样例

数据范围

• 对于前 $20\%$ 的数据，$n \le 7$；
• 对于前 $60\%$ 的数据，$n \le 5 \times 10^3$；
• 对于所有数据，$n \le 2 \times 10^5$。