Background

Qi is folding several freshly washed white shirts on the legs of a folding bed. He notices a sound behind him and turns his head to the back right.

Thinking it was "those guys outside," he does not deliberately hide his right eye—after all, nobody in the academy could come in.

He sees the boy with purple eyes; of course, Han also sees that flash of bright red.

"You didn't see anything."

Qi pretends to admire the sunset outside the window.

Problem Description

"There is no priceless information in this world," Qi shows a slightly satisfied smile.

"You know what I mean, right?"

Han withdraws his hand.

Qi gives Han the problem he left for him.

Since the violet and the red spider lily gave us different-colored pupils, we should naturally be connected. I call a set of points on a tree "connected" if and only if there exists a chain on the tree that can cover this set and the size of this set is at least $2$. We are unique, but you know, a tree is always connected.

"And then?"

"Now, you need to tell me, for each node, how many such sets contain it."

Qi drifts away.

That long-sealed memory of the city at the bottom of the lake is opened by a corner of the seal, by the power of the red spider lily and the violet.

Input Format

The first line contains a positive integer $n$, indicating that the tree has $n$ nodes labeled $1\sim n$.

The next $n-1$ lines each contain two positive integers $u, v$ describing an edge.

Output Format

To prevent the output from being too large, this problem uses the following output method.

Let $ans_i$ be the number of connected sets that contain node $i$, taken modulo $10^9+7$. You need to output the value of $\operatorname{xor}_{i=1}^n ans_i\times i$. Note that there is no modulo operation here.

4
1 2
2 3
2 4

18

Hint

Sample Explanation

Some connected sets are as follows:

• $\{1,2\}$
• $\{1,3\}$
• $\{1,4\}$
• $\{2,3\}$
• $\{2,4\}$
• $\{3,4\}$
• $\{1,2,3\}$
• $\{1,2,4\}$
• $\{2,3,4\}$

For example, $\{1,3,4\}$ is not a connected set, because you cannot find a chain such that $\{1,3,4\}$ is a subset of it.

Among them, nodes $1,2,3,4$ appear in $5,6,5,5$ sets respectively. By calculation, $\operatorname{xor}_{i=1}^n ans_i\times i=18$.

Constraints

This problem uses bundled testdata.

Special property $\text{A}$: It is guaranteed that the tree degenerates into a chain.

For $100\%$ of the testdata, $1\le u,v\le n\le5\times10^5$.

Translated by ChatGPT 5