#P18427. The Doubling Game 2

The Doubling Game 2

The Doubling Game 2

The Doubling Game 更像一道谜题。棋盘有 nn 个格子,编号为 1,2,…,n1,2,\ldots,n,用 n−1n-1 条线段连接,任意两个格子之间都能沿线段到达。因此,棋盘构成一棵树。初始时,每个顶点恰有一枚棋子。

唯一允许的操作是:选择通过一条线段直接相连、且棋子数相同的两个格子;两处的棋子数必须都是正数。把其中一个格子的全部棋子移动到另一个格子。

请计算执行任意次操作(也可以一次都不执行)后,棋盘可能出现多少种不同的棋子分布。如果两个分布至少有一个格子的棋子数不同,就认为它们不同。答案可能很大,只需输出它除以 109+710^9+7 的余数。

输入格式

第一行包含一个整数 nn(1≤n≤3⋅1051\le n\le3\cdot10^5),表示格子数。

接下来 n−1n-1 行,每行包含两个整数 ai,bia_i,b_i(1≤ai,bi≤n1\le a_i,b_i\le n,ai≠bia_i\ne b_i),表示这两个格子之间有一条线段。输入所描述的图是一棵树。

输出格式

输出一行一个整数,即不同棋子分布的数量对 109+710^9+7 取模的结果。

原样例

输入:

5
1 2
1 3
1 4
4 5

输出:

21

样例说明

样例棋盘及其顶点编号如下(原题配图):

原题样例棋盘

下面列出部分可以达到的分布,圆内的黑点表示棋子(原题配图,并非全部 21 种):

原题的部分可达棋面