{"raw_statement":[{"iden":"background","content":"玘正在折叠床脚几件刚洗净的白衬衫，他注意到身后的声响，向右后转头看去。\n\n以为是“外面的家伙”的他并没有刻意去遮掩自己的右眼——毕竟学院里的人不可能进来。\n\n他看见了那个紫眸的少年；当然寒也看见了那一瞬间的鲜红。\n\n「你什么都没看见。」\n\n玘装作欣赏窗外的晚霞。"},{"iden":"statement","content":"「世上没有无价的情报，」玘露出一丝满意的微笑。\n\n「你懂我的意思吧？」\n\n寒收回手。\n\n玘给出了他留给寒的题。\n\n> 既然紫堇和彼岸花给予了我们异色的瞳孔，我们理所应当是连接在一起的。我称**一棵树上的一个点集是“连接的”**，当且仅当**树上存在一条链能够覆盖这个点集并且这个集合大小不小于 $2$**。我们是独一无二的，可是你知道，一棵树，总是连起来的啊。\n\n「然后呢？」\n\n「现在，你需要告诉我每个点被多少个这样的点集所包含。」\n\n\n玘飘然而去。\n\n湖底之城那封存已久的记忆，被彼岸花和紫堇的力量，揭开了封印的一角。"},{"iden":"input","content":"第一行一个正整数 $n$ 表示这棵树有 $n$ 个点编号为 $1\\sim n$。\n\n接下来 $n-1$ 行，每行两个正整数 $u,v$ 描述一条边。"},{"iden":"output","content":"为了防止输出量过大，本题采用以下的输出方式。\n\n设 $ans_i$ 为包含 $i$ 号节点的连接的集合的个数对 $10^9+7$ 取模得到的值，你需要输出 $\\operatorname{xor}_{i=1}^n ans_i\\times i$ 的值。注意这里没有取模运算。"},{"iden":"note","content":"**样例解释**\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/rl9wkbww.png)\n\n**连接**的集合有以下一些：\n- $\\{1,2\\}$\n- $\\{1,3\\}$\n- $\\{1,4\\}$\n- $\\{2,3\\}$\n- $\\{2,4\\}$\n- $\\{3,4\\}$\n- $\\{1,2,3\\}$\n- $\\{1,2,4\\}$\n- $\\{2,3,4\\}$\n\n如 $\\{1,3,4\\}$ 就不是一个连接的集合，因为你找不出一条链使得 $\\{1,3,4\\}$ 为它的子集。\n\n其中 $1,2,3,4$ 号节点分别在 $5,6,5,5$ 个集合中出现。通过计算可得 $\\operatorname{xor}_{i=1}^n ans_i\\times i=18$。\n\n**数据范围**\n\n**本题采用捆绑测试。**\n\n| 子任务编号 | 数据范围 | 特殊性质 | 分值 | 时间限制 |\n| :----------: | :----------: | :----------: | :----------: | :-: |\n| $\\text{Subtask1}$ | $n\\le20$ | | $15$ | $\\text{1s}$ |\n| $\\text{Subtask2}$ | $n\\le100$ | | $15$  | $\\text{1s}$ |\n| $\\text{Subtask3}$ | $n\\le3\\times 10^3$ | | $20$ | $\\text{1s}$ |\n| $\\text{Subtask4}$ | $n\\le5\\times10^5$ | $\\text{A}$ | $15$ | $\\text{2s}$ |\n| $\\text{Subtask5}$ | $n\\le5\\times10^5$ | | $35$ | $\\text{2s}$ |\n\n特殊性质 $\\text{A}$：保证树退化成一条链。\n\n\n对于 $100\\%$ 的数据 $1\\le u,v\\le n\\le5\\times10^5$。"}],"translated_statement":null,"sample_group":[["4\n1 2\n2 3\n2 4","18"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}