题目内容

给你一棵有 $n$ 个节点的无向树。每条边有一个非负整数权值 $w$。请计算这棵树上所有简单路径的异或和之和。注意，本题中树为无向图，端点 $(u,v)$ 与 $(v,u)$ 视为同一路径，仅统计一次。

说明：路径指的是在树上选择两个节点作为端点的简单路径。当两个端点相同的时候，路径长度为 $0$ ，其异或和为 $0$ 。

【名词解释】

按位异或 $(BitwiseXOR)$：对两个整数的二进制表示按位进行异或运算。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T(1≤T≤2×10^5)$ 表示数据组数。除此之外，保证单个测试文件的 $n$ 之和不超过 $5×10^5$ 。每组测试数据的格式如下：

第一行输入一个整数 $n(1≤n≤2×10^5)$ ，表示节点数量；

此后 $n-1$ 行，每行输入三个整数 $u,v,w(1≤u,v≤n;0≤w≤10^9)$ 表示一条连接 $u$ 与 $v$ 的边及其权值。保证给出的是一棵树。

输出描述

对于每一组测试数据，新起一行输出一个整数，表示所有简单路径的异或和之和。若结果可能很大，请将答案对 $10^9+7$ 取模后输出。

样例1

输入

2
3
1 2 1
2 3 2
4
1 2 0
2 3 0
3 4 7

输出

6
21

说明

对于第一组：

• 树为 $1-2-3$，边权分别为 $1,2$ ；

• 所有端点对为 {$(1,2),(1,3),(2,3)$}，对应路径异或和依次为 $1,3,2$ ；

• 求和得到 $1+3+2=6$ 。