P2796 Facer's Programs

Facer is a cute coder. He wrote $N$ programs. The programs are cleverly related: any two programs are connected by exactly one chain. Specifically, for programs $a, b$, there exists and only exists one sequence $a,x_1,x_2,\dots ,x_n,b$ such that $a,x_1$ are directly connected, $x_1,x_2$ are directly connected, and so on, $x_n,b$ are directly connected. A set of programs that satisfies this is called a program block. Now, given the connections within one program block, determine how many sub-blocks it has. That is, choose a subset $S$ of programs such that $S$ also satisfies the condition above.

The first line contains a positive integer $N$. The next $N-1$ lines each contain two integers, representing two programs that are directly connected.

Output the number of sub-blocks, modulo $10^9+7$.

### Sample Explanation: The subsets $\{1\},\{2\},\{3\},\{1,2\},\{2,3\},\{1,2,3\}$ satisfy the condition above. ### Constraints For $10\%$ of the testdata, $1\le N\le20$. For $40\%$ of the testdata, $1\le N\le 500$. For $100\%$ of the testdata, $1\le N\le10^5$. Translated by ChatGPT 5