G. Xor-матическое число графа
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан неориентированный граф, состоящий из n вершин и m ребер. На каждом ребре написано целое неотрицательное число.

Назовем тройку чисел (u, v, s) интересной, если 1 ≤ u < v ≤ n и между вершинами u и v существует путь (необязательно простой, то есть может содержать какие-то вершины и рёбра по несколько раз), такой что xor чисел, написанных на рёбрах этого пути, равен s. При вычислении значения s для какого-нибудь пути, каждое ребро участвует в xor столько раз, сколько раз оно встречает на данном пути. Нетрудно доказать, что таких троек конечное количество.

Посчитайте сумму по модулю 109 + 7 значений числа s по всем интересным тройкам.

Входные данные

Первая строка входных данных содержит два числа n и m (1 ≤ n ≤ 100 000, 0 ≤ m ≤ 200 000) — количество вершин и рёбер в заданном графе.

Следующие m строк содержат по три целых числа ui, vi и ti (1 ≤ ui, vi ≤ n, 0 ≤ ti ≤ 1018, ui ≠ vi) — номера вершин, которые соединяет i-е ребро, и число, написанное на этом ребре. Гарантируется, что граф не содержит петель и кратных рёбер.

Выходные данные

Выведите единственное число, равное искомой сумме по модулю 109 + 7.

Примеры
Входные данные
4 4
1 2 1
1 3 2
2 3 3
3 4 1
Выходные данные
12
Входные данные
4 4
1 2 1
2 3 2
3 4 4
4 1 8
Выходные данные
90
Входные данные
8 6
1 2 2
2 3 1
2 4 4
4 5 5
4 6 3
7 8 5
Выходные данные
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)
Искомая сумма равна 1 + 2 + 3 + 3 + 2 + 1 = 12.

В втором примере существует 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)
Искомая сумма равна 1 + 2 + 3 + 4 + 6 + 7 + 8 + 9 + 11 + 12 + 13 + 14 = 90.