CF1299D 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 $ .

N/A

N/A

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.