Xor-matic Number of the Graph
Contest: Intel Code Challenge Final Round (Div. 1 + Div. 2, Combined)
Difficulty rating: 2600
Tags: bitmasks, graphs, math, number theory, trees

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.

Input format:
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 ui, vi and ti (1 ≤ ui, vi ≤ n, 0 ≤ ti ≤ 1018, ui ≠ vi) — vertices connected by the edge and integer written on it. It is guaranteed that graph doesn't contain self-loops and multiple edges.

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

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
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)

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)

Example input:
4 4
1 2 1
1 3 2
2 3 3
3 4 1

Example output:
12

Example input:
4 4
1 2 1
2 3 2
3 4 4
4 1 8

Example output:
90

Editorial:
Without loss of generality, let's assume that the graph is connected. If not, we will calculate the answer for each connected component and then sum them up.
Let's сhoose two arbitrary vertices u and v such that u < v and try to find all the interesting triples of the form (u,  v,  ...). Let's find any path p0, connecting these two vertices and calculate the xor of the numbers written on the edges of the path. Let's denote the obtained xor as s0.
Then take an arbitrary interesting triple (u,  v,  s1) and any path p1, with the xor of the numbers on it equals to s1. Consider the cycle of the following form: let's go through the first path p0, and then through the reversed direction of the second path p1. Thus, we will get a cycle containing the vertex u, with the xor of the numbers on it equals to $$s_0 \oplus s_1$$.
On the other hand, we can take any cycle which starts and ends in the vertex u, with the xor of the numbers on it equals to s2, and insert it before the path p0. Thus, we will get the path p2, with the xor of the numbers on it equals to $$s_{0} \oplus s_{2}$$, i.e. we will get an interesting triple $$( u, v, s_{0} \oplus s_{2} )$$.
Note that in the same manner we can add cycle, that doesn't pass through the vertex u. To do this, we can find any path from the vertex u to some of the vertices of the cycle, then go through the cycle itself, and then add the edges of same path in reversed order. As a result, all the edges of this path will be included in the resulting path twice and will not affect the resulting xor.
From this we get the following idea: for a fixed pair of vertices, we can find some path between them, and then add different cycles to it to obtain all interesting triples.
Basis of the cycle space of the graph can be obtained as follows: we find some spanning tree, and then for each edge, which is not included in that tree, add the cycle containing this edge and the path in the tree connecting its endpoints to the basis. For each cycle of the basis we will find xor of the numbers written in its edges.
Now, let's move from the operation of taking xor of numbers to the operations with vectors. To do this, we can represent all the numbers in the graph in the form of vectors of length 60, where i-th element of the vector will be equal to the value of the i-th bit in this number. Then taking xor of two numbers will be reduced to the addition of two vectors over the modulo 2. As a result, we can move from cycle space of the graph to the space $${\mathbb Z}_{2}^{60}$$.
A linear combination of cycles of the graph, gives us a linear combination of vectors corresponding to xor of the numbers on the edges of the cycles. The set of linear combinations of the vectors form a subspace of $${\mathbb Z}_{2}^{60}$$. We can find the basis of this subspace using Gaussian elimination.
Let's denote the dimension of the basis as r. Then, for every pair of vertices u and v, the amount of interest triples for these vertices is equal to 2r, and all values of the parameter s for these triples can be obtained by adding the vector corresponding to an arbitrary path between these vertices to the described subspace.
Let's choose a pair of vertices u and v and some bit i and count how many times the value of 2i will appear in the resulting sum. Let's assume that the value of the i-th bit on the path between the chosen vertices is equal to b. If i-th bit is equal to one for at least one vector of the basis, then this bit will be equal to one in the 2r - 1 triples. Otherwise, i-th bit in all the 2r triples will be equal to b.
Let's start the depth first search from some vertex fixed vertex r, and find a paths to each vertex of the graph. For each of this paths we calculate the value of xor of the numbers on them. For each bit i let's count how many times it was equal to zero and one on these paths (denote this numbers zeroi and onei).
Then, for a fixed bit i, for exactly zeroi * onei pairs of vertices it will be equal to one on the path connecting this vertices, and for $${ \binom { zero_{i} } { 2 } } + { \binom { one_{i} } { 2 } }$$ pairs it will be zero.
Thus, if the i-th bit is equal to one in at least one vector from the basis, we should add $$2^{i} * \binom{n}{2} * 2^{r-1}$$ to the answer. In the other case, if bits i is equal to zero for all vectors from the basis, we should add 2i * zeroi * onei * 2r to the answer.
The resulting complexity of this solution is O(m * log 1018).