该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

注意：

• 英文题目名称即文件名，若文件名为 filename，则提交的文件为filename.pas/c/cpp，程序输入输出文件名分别为 filename.in filename.out。
• 建议时限仅供参考，具体按照评测机上标程运行时间的2 - 3倍设置。
• 建议将栈大小设为64m，并打开编译参数O2。

树上的距离

题目限制

1000 ms 256 M

题目描述

一个 $n$ 个节点的树（编号 $1\sim n$ ）。对于树上一对顶点 $(x,y)$ ，我们定义两点之间的距离为：从 $x$ 到 $y$ 的路径（简单路径）中所有边的权值的异或（ $xor$ ）。

求所有点对之间距离的和。由于结果太大，只需要输出对 $1e9+7$ 取模的结果。

输入格式

第一行输入一个正整数n，表示树上节点的数量。（2≤n≤200000） 之后n-1行，每行输入三个整数u,v,w。表示一条点u,v间的双向边，其权值为w。

输出格式

输出所有点对之间距离的和对 1e9+7 取模的结果。

数据范围

对于23%的数据，$2 \le n \le 10$；

对于33%的数据，$2 \le n \le 1000$；

对于100%的数据，$2 \le n \le 2 \times 10^5, 1 \le u, v \le n, 0 \le w \lt 2^{60}$，保证给出的图是一棵树。

输入样例

3
1 2 1
1 3 3

输出样例

6