CF724G.Xor-matic Number of the Graph

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 < 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 109 + 7 of the values of s over all interesting triples.

给你一个包含 $n$ 个顶点和 $m$ 条边的无向图。图中每条边上都写有一个非负整数。

我们称一个三元组 $(u,\,v,\,s)$ 是有趣的，当且仅当 $1 \le u < v \le n$，且在顶点 $u$ 和 $v$ 之间存在一条路径（该路径可以是非简单的，即允许重复访问顶点和边），使得该路径上所有边所写数字的异或（xor）值等于 $s$。在计算某条路径对应的 $s$ 值时，路径中每条边在异或运算中出现多少次，就参与异或多少次。不难证明，这样的三元组的总数是有限的。

请计算所有有趣三元组 $(u,\,v,\,s)$ 中的 $s$ 值之和，并对 $10^9 + 7$ 取模。

The first line of the input contains two integers n and m (1 ≤ n ≤ 100 000, 0 ≤ m ≤ 200 000) — 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 ≤ 1018, 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.

输入的第一行包含两个整数 $n$ 和 $m$（$1 ≤ n ≤ 100\,000$，$0 ≤ m ≤ 200\,000$）—— 分别表示给定图中的顶点数和边数。

接下来的 $m$ 行每行包含三个整数 $u_i$、$v_i$ 和 $t_i$（$1 ≤ u_i,\,v_i ≤ n$，$0 ≤ t_i ≤ 10^{18}$，$u_i ≠ v_i$）—— 表示该边所连接的两个顶点以及边上所写的整数。保证图中不含自环和重边。

Print the single integer, equal to the described sum over modulo 109 + 7.

输出单个整数，即所描述的和对 $10^9 + 7$ 取模的结果。

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.

在第一个例子中，有 6 个有趣的三元组：

1. $(1,\,2,\,1)$
2. $(1,\,3,\,2)$
3. $(1,\,4,\,3)$
4. $(2,\,3,\,3)$
5. $(2,\,4,\,2)$
6. $(3,\,4,\,1)$

它们的和为 $1\,+\,2\,+\,3\,+\,3\,+\,2\,+\,1\,=\,12$。

在第二个例子中，有 12 个有趣的三元组：

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)$

它们的和为 $1\,+\,2\,+\,3\,+\,4\,+\,6\,+\,7\,+\,8\,+\,9\,+\,11\,+\,12\,+\,13\,+\,14\,=\,90$。