Around the World

题意翻译

给定一张无向联通图，大小为 $n$ ，有 $m$ 条边，每条边有边权，保证无重边自环。 **同时保证，不存在一个长度 $>3$ 的简单环经过了 $1$ 号点。** 你需要求解，有多少种方案删除若干条与 $1$ 号节点相连的边，使得不存在任意一条路径（不一定是简单路径）满足下列 $3$ 个条件： * 其以 $1$ 号节点为起点，$1$ 号节点为终点。 * 此路径经过的所有边的边权异或和为 $0$ 。 * 其至少经过了一条边奇数次。 你需要输出这个方案数对 $10^9+7$ 取模的结果。 $n,m\le 10^5,w\le 31$。

题目描述

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

输入输出样例

输入样例 #1

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

输出样例 #1

2

输入样例 #2

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

输出样例 #2

1

输入样例 #3

4 4
1 2 27
1 3 1
1 4 1
3 4 0

输出样例 #3

6

说明

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.

题意翻译

给定一张无向联通图，大小为 $n$ ，有 $m$ 条边，每条边有边权，保证无重边自环。 **同时保证，不存在一个长度 $>3$ 的简单环经过了 $1$ 号点。** 你需要求解，有多少种方案删除若干条与 $1$ 号节点相连的边，使得不存在任意一条路径（不一定是简单路径）满足下列 $3$ 个条件： * 其以 $1$ 号节点为起点，$1$ 号节点为终点。 * 此路径经过的所有边的边权异或和为 $0$ 。 * 其至少经过了一条边奇数次。 你需要输出这个方案数对 $10^9+7$ 取模的结果。 $n,m\le 10^5,w\le 31$。