Guy-Manuel 和 Thomas 正在计划 $$$144$$$ 的环球旅行。
给定一个简单的带权无向连通图,其中有 $$$n$$$ 个顶点和 $$$m$$$ 条边,并具有以下限制:不存在任何长度大于 $$$3$$$ 且穿过顶点 $$$1$$$ 的简单循环(即,不会多次通过任何顶点的循环)。该图中路径(不一定简单)的成本定义为该路径中所有边的权重的异或,每条边的计数次数与路径经过它的次数相同。
但是花费 $$$0$$$ 的旅行并不令人兴奋。
您可以选择与顶点 $$$1$$$ 关联的边的任何子集并将其删除。有多少这样的子集,当删除时,不存在任何成本等于 $$$0$$$ 的非平凡循环,该循环通过结果图中的顶点 $$$1$$$ ?如果一个循环通过某个边奇数次,则该循环被称为非平凡循环。由于答案可能非常大,因此输出它对 $$$10^9+7$$$ 取模。
输入
第一行包含两个整数 $$$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 < 32$$$) — 第 $$$i$$$ 条边的端点及其重量。保证不存在任何重边,图是连通的,并且不存在任何长度大于 $$$3$$$ 的简单循环穿过顶点 $$$1$$$。
输出
输出对 $$$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
注意
下图代表示例中的图表。 在第一个示例中,不存在任何成本为 $$$0$$$ 的非平凡循环,因此我们可以删除或保留与顶点 $$$1$$$ 相关的唯一边。 在第二个例子中,如果我们不删除边$$$1-2$$$,则存在一个循环$$$1-2-4-5-2-1$$$,成本为$$$0$$$;另外,如果我们不删除边$$$1-3$$$,则存在成本$$$0$$$的循环$$$1-3-2-4-5-2-3-1$$$。唯一有效的子集由两条边组成。 在第三个示例中,除了保留边 $$$1-3$$$ 和 $$$1-4$$$ 的两个子集之外,所有子集均有效。