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

Guy-Manuel 和 Thomas 正在计划环游世界的 $144$ 次旅行。

给定一个含 $n$ 个顶点和 $m$ 条边的简单带权无向连通图，满足如下限制条件：不存在长度大于 $3$ 的、经过顶点 $1$ 的简单环（即不重复经过任一顶点的环）。图中一条路径（不一定是简单路径）的代价定义为该路径中所有边的权重的 异或（XOR），其中每条边的权重在异或运算中出现的次数等于该路径经过该边的次数。

但代价为 $0$ 的旅行并不令人兴奋。

你可以任选顶点 $1$ 所关联的一组边并将其全部删除。问：有多少种这样的边子集，使得删除后所得图中不存在任何经过顶点 $1$ 的、代价为 $0$ 的非平凡环？若一个环经过某条边的次数为奇数，则称该环为非平凡环。由于答案可能非常大，请将结果对 $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 \lt 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$.

第一行包含两个整数 $n$ 和 $m$（$1 \le n,m \le 10^5$），分别表示图中顶点和边的数量。接下来的 $m$ 行中，第 $i$ 行包含三个整数 $a_i$、$b_i$ 和 $w_i$（$1 \le a_i, b_i \le n$，$a_i \neq b_i$，$0 \le w_i \lt 32$），表示第 $i$ 条边的两个端点及其权重。保证图中不存在重边，图是连通的，且不存在长度大于 $3$ 且经过顶点 $1$ 的简单环。

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

以 $10^9+7$ 为模输出答案。

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.

下方图片展示了示例中的图。

在第一个示例中，不存在任何非平凡的零代价环（nontrivial cycles with cost $0$），因此我们可以选择删除或保留唯一与顶点 $1$ 关联的边。

在第二个示例中，若不删除边 $1\text{-}2$，则存在一个零代价环 $1\text{-}2\text{-}4\text{-}5\text{-}2\text{-}1$；同样，若不删除边 $1\text{-}3$，则存在一个零代价环 $1\text{-}3\text{-}2\text{-}4\text{-}5\text{-}2\text{-}3\text{-}1$。唯一合法的边子集即为同时包含这两条边的子集。

在第三个示例中，除同时保留边 $1\text{-}3$ 和 $1\text{-}4$ 的两个子集外，其余所有子集均合法。