A13199 | Around the World

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](https://en.wikipedia.org/wiki/Bitwise_operation#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$ .

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 the answer modulo $10^9+7$ .