该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定一棵有 n 个结点的树，1 号点为这棵树的根。请统计这棵树有多少连通块。由于答案可能很大，输出答案模 1,000,000,007 的余数即可。

连通块是指树上结点的集合，用树上的边可以将这些点全部连通，且不需要经过块外的点。

在这题里，空集不算连通块。

输入格式

第一行：单个整数表示 n； 接下来 n-1行每行两个整数 ui 和 vi，代表一条边连接， 中间用一个空格分开。

输出格式

一行 $n$ 个数，为 $1 \sim n$。

3
1 2
1 3

6

样例1解释

{1}、{2}、{3}、{1 2}、{1 3}、{1 2 3}

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

62

样例2解释

{4}、 {5}、 {6}、 {7}、 {8}、

{2}、 {24}、 {25}、 {245}、

{3}、 {36}、 {37}、 {38}、 {367}、 {368}、 {378}、 {3678}、

{1}、 {12}、 {124}、 {125}、 {1245}、

{13}、 {123}、 {1234}、 {1235}、 {12345}、

{136}、 {1236}、 {12346}、 {12356}、 {123456}、

{137}、 {1237}、 {12347}、 {12357}、 {123457}、

{138}、 {1238}、 {12348}、 {12358}、 {123458}、

{1367}、 {12367}、 {123467}、 {123567}、 {1234567}、

{1368}、 {12368}、 {123468}、 {123568}、 {1234568}、

{1378}、 {12378}、 {123478}、 {123578}、 {1234578}、

{13678}、 {123678}、 {1234678}、 {1235678}、 {12345678}

数据规模与约定

对于 $100\%$ 的数据，$0 \le n \le 2*10^5$。