← 返回题目列表

Codeforces · 724/G

G. 图形的 Xor-matic 编号

中文机器翻译题面 查看原题

给定一个无向图,由 n 个顶点和 m 个边组成。图的每条边上都写有一些非负整数。

让我们称三元组 (u, v, s) 有趣,如果 1 ≤ u < v ≤ n 并且在顶点 u 和 v 之间存在一条路径(可能是非简单的,即它可以多次访问相同的顶点和边),使得写在该路径的边上的所有数字的异或等于 s。当我们计算某个路径的值 s 时,每条边在异或中的计数次数与该路径上出现的次数相同。不难证明这样的三元组的数量是有限的。

计算所有感兴趣的三元组的 s 值模 109 + 7 的总和。

输入

输入的第一行包含两个整数 n 和 m (1 ≤ n ≤ 100 000, 0 ≤ m ≤ 200 000) - 给定图中的顶点和边的数量。

接下来的 m 行包含三个整数 ui、vi 和 ti (1 ≤ ui, vi ≤ n, 0 ≤ ti ≤ 1018, ui ≠ vi) - 由边和上面写的整数连接的顶点。保证图不包含自环和重边。

输出

打印单个整数,等于所描述的模 109 + 7 的总和。

示例

输入 #1

4 4
1 2 1
1 3 2
2 3 3
3 4 1

输出 #1

12

输入 #2

4 4
1 2 1
2 3 2
3 4 4
4 1 8

输出 #2

90

输入 #3

8 6
1 2 2
2 3 1
2 4 4
4 5 5
4 6 3
7 8 5

输出 #3

62

注意

在第一个示例中,有 6 个有趣的三元组:

1. (1, 2, 1)
2. (1, 3, 2)
3. (1, 4, 3)
4. (2, 3, 3)
5. (2, 4, 2)
6. (3, 4, 1)

在第二个示例中,有 12 个有趣的三元组:

1. (1, 2, 1)
2. (2, 3, 2)
3. (1, 3, 3)
4. (3, 4, 4)
5. (2, 4, 6)
6. (1, 4, 7)
7. (1, 4, 8)
8. (2, 4, 9)
9. (3, 4, 11)
10. (1, 3, 12)
11. (2, 3, 13)
12. (1, 2, 14)