Xor-matic Number of the Graph

题意翻译

### 题目描述 给你一个无向图，有n个顶点和m条边，每条边上都有一个非负权值。 我们称一个三元组 $(u,v,s)$ 是有趣的，当且仅当对于 $1 \le u < v \le n$ 且有一条从 $u$ 到 $v$ 的路径(可以经过相同的点和边多次)，其路径上的权值异或和为 $s$。对于一条路径，如果一条边经过了多次，则计算异或和时也应计算多次。不难证明，这样的三元组是有限的。 计算所有有趣的三元组中 $s$ 的和对于 $10^9+7$ 的模数 ### 输入输出格式 **输入格式：** 第一行包括两个整数 $n,m,(n\in [1,10^5],m\in[0,2*10^5]$ ——图中点数与边数 接下来的 $m$ 行每行包括3个整数 $u_i,v_i,t_i(u_i,v_i\in [1,n],t_i\in [0,10^{18}],u_i\not = v_i)$ ——边的两端点序号与边的权值 图中无自环与重边 **输出格式：** 输出一个整数，即题目中的答案对于 $10^9+7$ 的mod值 感谢@Dimitry_L 提供的翻译

题目描述

You are given an undirected graph, constisting of $ n $ vertices and $ m $ edges. Each edge of the graph has some non-negative integer written on it. Let's call a triple $ (u,v,s) $ interesting, if $ 1<=u&lt;v<=n $ and there is a path (possibly non-simple, i.e. it can visit the same vertices and edges multiple times) between vertices $ u $ and $ v $ such that xor of all numbers written on the edges of this path is equal to $ s $ . When we compute the value s for some path, each edge is counted in xor as many times, as it appear on this path. It's not hard to prove that there are finite number of such triples. Calculate the sum over modulo $ 10^{9}+7 $ of the values of $ s $ over all interesting triples.

输入输出格式

输入格式

The first line of the input contains two integers $ n $ and $ m $ ( $ 1<=n<=100000 $ , $ 0<=m<=200000 $ ) — numbers of vertices and edges in the given graph. The follow $ m $ lines contain three integers $ u_{i} $ , $ v_{i} $ and $ t_{i} $ ( $ 1<=u_{i},v_{i}<=n $ , $ 0<=t_{i}<=10^{18} $ , $ u_{i}≠v_{i} $ ) — vertices connected by the edge and integer written on it. It is guaranteed that graph doesn't contain self-loops and multiple edges.

输出格式

Print the single integer, equal to the described sum over modulo $ 10^{9}+7 $ .

输入输出样例

输入样例 #1

4 4
1 2 1
1 3 2
2 3 3
3 4 1

输出样例 #1

12

输入样例 #2

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

输出样例 #2

90

输入样例 #3

8 6
1 2 2
2 3 1
2 4 4
4 5 5
4 6 3
7 8 5

输出样例 #3

62

说明

In the first example the are $ 6 $ interesting triples: 1. $ (1,2,1) $ 2. $ (1,3,2) $ 3. $ (1,4,3) $ 4. $ (2,3,3) $ 5. $ (2,4,2) $ 6. $ (3,4,1) $ The sum is equal to $ 1+2+3+3+2+1=12 $ .In the second example the are $ 12 $ interesting triples: 1. $ (1,2,1) $ 2. $ (2,3,2) $ 3. $ (1,3,3) $ 4. $ (3,4,4) $ 5. $ (2,4,6) $ 6. $ (1,4,7) $ 7. $ (1,4,8) $ 8. $ (2,4,9) $ 9. $ (3,4,11) $ 10. $ (1,3,12) $ 11. $ (2,3,13) $ 12. $ (1,2,14) $ The sum is equal to $ 1+2+3+4+6+7+8+9+11+12+13+14=90 $ .