题目描述

我们有一颗包含 $N$ 个节点的带权树。第 $i$ 条边双向连接了节点 $u_i$ 和节点 $v_i$，边的权重为 $w_i$。

对于节点对 $(x,y)$，我们定义 $\\text{dist}(x,y)$ 如下：

• 从 $x$ 到 $y$ 的最短路径上所有边的权重的异或和。

找到所有节点对 $(i,j)$ $(1 \\leq i \\lt j \\leq N)$ 的 $\\text{dist}(i,j)$，并将这些值按照 $(10^9+7)$ 取模后的和打印出来。

什么是异或和？

整数 $A$ 和 $B$ 的异或和，记为 $A\\ \\mathrm{XOR}\\ B$，定义如下：

• 当用二进制表示 $A\\ \\mathrm{XOR}\\ B$ 时，如果 $A$ 和 $B$ 中恰好有一个数位是 $1$，那么在对应的数位上，$A\\ \\mathrm{XOR}\\ B$ 的数位是 $1$，否则为 $0$。

例如，$3\\ \\mathrm{XOR}\\ 5 = 6$（在二进制中：$011\\ \\mathrm{XOR}\\ 101 = 110$）。

约束条件

• $2 \\leq N \\leq 2 \\times 10^5$
• $1 \\leq u_i \\lt v_i \\leq N$
• $0 \\leq w_i \\lt 2^{60}$
• 给定的图是一棵树。
• 输入中的所有值都是整数。

输入

输入的格式如下，从标准输入中给出：

$N$ $u_1$ $v_1$ $w_1$ $u_2$ $v_2$ $w_2$ $\\vdots$ $u_{N-1}$ $v_{N-1}$ $w_{N-1}$

输出

打印 $\\text{dist}(i,j)$ 的和，模 $(10^9+7)$ 后的结果。

示例输入 1

3
1 2 1
1 3 3

示例输出 1

6

我们有 $\\text{dist}(1,2)=1$，$\\text{dist}(1,3)=3$，$\\text{dist}(2,3)=2$，它们的和为 $6$。

示例输入 2

5
3 5 2
2 3 2
1 5 1
4 5 13

示例输出 2

62

示例输入 3

10
5 7 459221860242673109
6 8 248001948488076933
3 5 371922579800289138
2 5 773108338386747788
6 10 181747352791505823
1 3 803225386673329326
7 8 139939802736535485
9 10 657980865814127926
2 4 146378247587539124

示例输出 3

241240228

打印 $\\text{dist}(i,j)$ 的和，模 $(10^9+7)$ 后的结果。