题目内容

有一棵包含 $n$ 个节点的无向树，节点编号为 $1$ 到 $n$。树上每条边带有一个非负整数权值 $w$。

定义一种运算 $\oplus$，称为“按位差异运算”：对于两个整数 $a$ 和 $b$，将它们的二进制表示逐位比较，如果某一位不同，则结果在该位取 $1$，否则取 $0$，最终得到的新整数即为 $a \oplus b$。

对于树上任意两个节点 $u$ 和 $v$，它们之间的唯一路径上所有边权依次进行按位差异运算，得到的值称为该节点对的“路径差异值”。特别地，若 $u = v$，路径差异值视为 $0$。

请你计算树上所有无序节点对 $(u,v)$（$(u,v)$ 与 $(v,u)$ 算作同一对）的路径差异值之和。由于答案可能较大，请将结果对 $10^9+7$ 取模后输出。

节点个数 $n$ 满足 $1 \le n \le 2 \times 10^5$。测试数据组数 $T$ 满足 $1 \le T \le 2 \times 10^5$，且所有测试数据中 $n$ 的总和不超过 $5 \times 10^5$。所有边权满足 $0 \le w \le 10^9$。

输入描述

第一行输入一个整数 $T$，表示测试数据组数。接下来依次输入每组数据。

每组数据的格式如下： 第一行一个整数 $n$，表示树的节点个数。 接下来 $n-1$ 行，每行三个整数 $u, v, w$，表示一条连接节点 $u$ 与节点 $v$ 的边，其权值为 $w$。

保证输入构成一棵树，且所有测试数据的 $n$ 之和不超过 $5 \times 10^5$。

输出描述

对于每组测试数据，输出一行一个整数，表示所有无序节点对的路径差异值之和对 $10^9+7$ 取模后的结果。

样例1

输入

1
2
1 2 5

输出

5

说明

只有节点 1 和 2，路径差异值为边权 $5$。所有无序对仅有一对 $(1,2)$，故总和为 5。

样例2

输入

1
4
1 2 0
2 3 3
3 4 4

输出

24

说明

设根节点为 1，计算各节点到根的路径异或值 $pre$：$pre[1]=0$，$pre[2]=0$，$pre[3]=3$，$pre[4]=3 \oplus 4=7$。 所有无序节点对共 $\binom{4}{2}=6$ 对： $(1,2): 0 \oplus 0 =0$; $(1,3): 0 \oplus 3 =3$; $(1,4): 0 \oplus 7 =7$; $(2,3): 0 \oplus 3 =3$; $(2,4): 0 \oplus 7 =7$; $(3,4): 3 \oplus 7 =4$. 总和为 $0+3+7+3+7+4=24$。 也可按位统计：pre 数组中 1 的个数对每位贡献求和同样得到 24。

样例3

输入

1
5
1 2 1
2 3 2
3 4 4
4 5 8

输出

72

说明

边权依次为 $1,2,4,8$，恰对应二进制各位。根为 1，各节点 $pre$：$pre[1]=0$, $pre[2]=1$, $pre[3]=1\oplus 2=3$, $pre[4]=3\oplus 4=7$, $pre[5]=7\oplus 8=15$。 节点对共有 $\binom{5}{2}=10$ 对，计算各对的异或值： $(1,2):0\oplus1=1$; $(1,3):3$; $(1,4):7$; $(1,5):15$; $(2,3):1\oplus3=2$; $(2,4):6$; $(2,5):14$; $(3,4):4$; $(3,5):12$; $(4,5):8$。 总和为 $1+3+7+15+2+6+14+4+12+8=72$。 按位统计：第 $0$ 位 $cnt_1=4, cnt_0=1$ 贡献 $4\times 1=4$; 第 $1$ 位 $cnt_1=3,cnt_0=2$ 贡献 $6\times 2=12$; 第 $2$ 位 $cnt_1=2,cnt_0=3$ 贡献 $6\times 4=24$; 第 $3$ 位 $cnt_1=1,cnt_0=4$ 贡献 $4\times 8=32$。总和 $4+12+24+32=72$。