Description

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.

Input Format

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 Format

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

3
1 2
2 3

6

Hint

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