P2796 Facer的程序
题目描述
Facer 是一个萌萌哒的码农。他写了 $N$ 个程序。程序和程序之间有巧妙的联系,即任意两个程序恰好由一条联系链连在一起。
具体来说,对于程序 $a,b$,存在且仅存在一个序列 $a,x_1,x_2,\dots ,x_n,b$,使得 $a,x_1$ 有联系, $x_1,x_2$ 有联系,依此类推,$x_n,b$ 有联系。符合这样的一组程序称为程序块。
现在已知一个程序块的程序之间的联系,询问它有多少个子程序块。即取出一个程序子集 $S$,使得 $S$ 也满足上述条件。
输入格式
第一行输入一个正整数 $N$。
接下来 $N-1$ 行,每行两个数,代表有联系的两个程序。
输出格式
输出有多少个子程序块,对 $10^9+7$ 取模。
说明/提示
### 样例解释:
子集 $\{1\},\{2\},\{3\},\{1,2\},\{2,3\},\{1,2,3\}$ 满足上述条件。
### 数据范围
对于 $10\%$ 的数据 $1\le N\le20$。
对于 $40\%$ 的数据 $1\le N\le 500$。
对于 $100\%$ 的数据 $1\le N\le10^5$。