Вам дан неориентированный граф, состоящий из n вершин и m ребер. На каждом ребре написано целое неотрицательное число.
Назовем тройку чисел (u, v, s) интересной, если 1 ≤ u < v ≤ n и между вершинами u и v существует путь (необязательно простой, то есть может содержать какие-то вершины и рёбра по несколько раз), такой что xor чисел, написанных на рёбрах этого пути, равен s. При вычислении значения s для какого-нибудь пути, каждое ребро участвует в xor столько раз, сколько раз оно встречает на данном пути. Нетрудно доказать, что таких троек конечное количество.
Посчитайте сумму по модулю 109 + 7 значений числа s по всем интересным тройкам.
Выходные данные
Выведите единственное число, равное искомой сумме по модулю 109 + 7.
Примечание
В первом примере существует 6 интересных троек:
- (1, 2, 1)
- (1, 3, 2)
- (1, 4, 3)
- (2, 3, 3)
- (2, 4, 2)
- (3, 4, 1)
Искомая сумма равна
1 + 2 + 3 + 3 + 2 + 1 = 12.
В втором примере существует 12 интересных троек:
- (1, 2, 1)
- (2, 3, 2)
- (1, 3, 3)
- (3, 4, 4)
- (2, 4, 6)
- (1, 4, 7)
- (1, 4, 8)
- (2, 4, 9)
- (3, 4, 11)
- (1, 3, 12)
- (2, 3, 13)
- (1, 2, 14)
Искомая сумма равна
1 + 2 + 3 + 4 + 6 + 7 + 8 + 9 + 11 + 12 + 13 + 14 = 90.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 4
1 2 1
1 3 2
2 3 3
3 4 1
|
12
|
|
2
|
4 4
1 2 1
2 3 2
3 4 4
4 1 8
|
90
|
|
3
|
8 6
1 2 2
2 3 1
2 4 4
4 5 5
4 6 3
7 8 5
|
62
|