Around the World
Contest: Codeforces Round 618 (Div. 1)
Difficulty rating: 3000
Tags: bitmasks, combinatorics, dfs and similar, dp, graphs, graphs, math, trees

Guy-Manuel and Thomas are planning $$$144$$$ trips around the world.

You are given a simple weighted undirected connected graph with $$$n$$$ vertexes and $$$m$$$ edges with the following restriction: there isn't any simple cycle (i. e. a cycle which doesn't pass through any vertex more than once) of length greater than $$$3$$$ which passes through the vertex $$$1$$$. The cost of a path (not necessarily simple) in this graph is defined as the XOR of weights of all edges in that path with each edge being counted as many times as the path passes through it.

But the trips with cost $$$0$$$ aren't exciting.

You may choose any subset of edges incident to the vertex $$$1$$$ and remove them. How many are there such subsets, that, when removed, there is not any nontrivial cycle with the cost equal to $$$0$$$ which passes through the vertex $$$1$$$ in the resulting graph? A cycle is called nontrivial if it passes through some edge odd number of times. As the answer can be very big, output it modulo $$$10^9+7$$$.

Input format:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n,m \le 10^5$$$) — the number of vertexes and edges in the graph. The $$$i$$$-th of the next $$$m$$$ lines contains three integers $$$a_i$$$, $$$b_i$$$ and $$$w_i$$$ ($$$1 \le a_i, b_i \le n, a_i \neq b_i, 0 \le w_i < 32$$$) — the endpoints of the $$$i$$$-th edge and its weight. It's guaranteed there aren't any multiple edges, the graph is connected and there isn't any simple cycle of length greater than $$$3$$$ which passes through the vertex $$$1$$$.

Output format:
Output the answer modulo $$$10^9+7$$$.

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

Note:
The pictures below represent the graphs from examples.  In the first example, there aren't any nontrivial cycles with cost $$$0$$$, so we can either remove or keep the only edge incident to the vertex $$$1$$$.  In the second example, if we don't remove the edge $$$1-2$$$, then there is a cycle $$$1-2-4-5-2-1$$$ with cost $$$0$$$; also if we don't remove the edge $$$1-3$$$, then there is a cycle $$$1-3-2-4-5-2-3-1$$$ of cost $$$0$$$. The only valid subset consists of both edges.  In the third example, all subsets are valid except for those two in which both edges $$$1-3$$$ and $$$1-4$$$ are kept.

Example input:
6 8
1 2 0
2 3 1
2 4 3
2 6 2
3 4 8
3 5 4
5 4 5
5 6 6

Example output:
2

Example input:
7 9
1 2 0
1 3 1
2 3 9
2 4 3
2 5 4
4 5 7
3 6 6
3 7 7
6 7 8

Example output:
1

Editorial:
It's common knowledge that in an undirected graph there is some subset (not necessarily unique) of simple cycles called basis such that any Eulerian subgraph (in connected graphs also known as a cyclic path) is a xor-combination of exactly one subset of basis cycles. In a given connected graph consider any spanning tree; any edge which isn't in that spanning tree forms a cycle with some tree's edges of some cost $$$c$$$. These cycles form the basis. A cost of a cyclic path is an XOR of costs of basis cycles that form this path. Now we can move from cycle space to the space of $$$5$$$-dimensional vectors $$$\mathbb{Z}_2^5$$$. If the costs of basis cycles are linear dependent, then there is a cycle of cost $$$0$$$, else they form the basis of some subspace of $$$\mathbb{Z}_2^5$$$.
In the given graph there are two types of "components" connected to $$$1$$$, and after removing the edges each component contributes some subspace (possibly an empty one); these subspaces shouldn't intersect. These two types are components connected with an edge and components connected with two edges:

In the first picture, the basis cycles are formed by the blue edges. We can cut the edge incident to $$$1$$$ or keep it; if we don't cut that edge, this component contributes a subspace formed by costs of basis cycles unless they are linear dependent, else it contributes the empty subspace.
In the second picture, the basis cycles are formed by the blue edges and the red edge. We can cut both edges, and then this component contributes an empty subspace; if we cut one edge, the red edge moves to the spanning tree and no longer form a basis cycle, so this component contributes a subspace formed by costs of basis cycles formed by blue edges; if we don't cut any edges, then this component contributes a subspace formed by costs of basis cycles formed by blue and red edges.
If any choice leads to keeping a set of linear dependent basis cycles' costs, then this choice is invalid.
Now for every component, we have from $$$1$$$ to $$$4$$$ valid choices of choosing the contributing subspace. There are $$$374$$$ subspaces of $$$\mathbb{Z}_2^5$$$, which can be precalculated as well as their sums. Now we can calculate a dp $$$dp_{i,j}$$$ — the number of ways to get the subspace $$$j$$$ using the first $$$i$$$ components. The transitions are obvious: if we can get the subspace $$$X$$$ at the $$$i$$$-th component, then for each existing subspace $$$Y$$$, if $$$X$$$ and $$$Y$$$ don't intersect, do $$$dp_{i,X+Y} := dp_{i,X+Y} + dp_{i-1,Y}$$$, where $$$X+Y$$$ is the sum of subspaces. The answer is a sum of dp values for the last component.