题目描述

Sam 最近又又又在复习图论了！在复习 $spfa$ 的时候，他看到了一种图——菊花图。

菊花图是一种很有趣的图，它的形状类似于一朵菊花，正中间一个点，然后这个点和其他所有点存在一条边相连：

于是 Sam 突发奇想，如果存在一种不那么标准的菊花图呢？

也就是正中间依旧是一个点，但是这个点连接出去的点可以向外继续延伸，比如下图：

形式化的说，也就是在一个连通图 $G$ 中，当且仅当 $G$ 存在恰好一个度数 $\ge 3$ 的点，那么 Sam 就认为 $G$ 是一个星形图。

现在 Sam 准备给你降低一点难度，他打算给你一棵包含了 $n$ 个点的树，希望你删除其中一部分点（可以不删，但不能产生超过一个连通块）后，使得剩余的点会变成一个星形图。

请你告诉 Sam 有多少种不同的方案。

输入格式

输入第一行包含一个整数 $n$，表示这棵树的节点数量。

接下来 $n-1$ 行每行包含两个整数 $u,v$ 表示一条树边。

输出格式

输出第一行包含一个整数，表示方案数，由于答案可能过大，请你将答案对 $1e9+7$ 取模后输出。

输入输出样例 #1

输入 #1

6
1 2
1 3
1 4
1 5
1 6

输出 #1

16

输入输出样例 #2

输入 #2

6
1 2
1 3
1 4
3 5
3 6

输出 #2

6

说明/提示

数据范围

对于 $20\%$ 的数据满足 $n \le 15$。

对于 $40\%$ 的数据满足 $n \le 2000$。

对于另外 $10\%$ 的数据满足 $u_i=i,v_i=i+1$。

对于另外 $10\%$ 的数据满足 $u_i=1,v_i=i+1$。

对于另外 $10\%$ 的数据保证给定的树为星形图。

对于所有数据满足：$1 \leq n \leq 5 \times 10^5$，且保证给定的边构成一棵树。

样例解释1

由于本身就是一个星形图，所以除 $1$ 之外只要保留任意 $3$ 个节点都是一组可行方案。

• 不删的方案为 $1$。
• 删 $1$ 个点的方案为 $5$。
• 删 $2$ 个点的方案为 $5 * 4 / 2 = 10$。
• 一共有 $16$ 种方案。

样例解释2

如果以 $1$ 为中心点，$5,6$ 至少删一个即可，有 $3$ 种方案。

如果以 $3$ 为中心点，$2,4$ 至少删一个即可，有 $3$ 种方案。

一共 $6$ 种方案。