C. Счастливое дерево
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

Петя любит счастливые числа. Всем известно, что счастливыми являются положительные целые числа, в десятичной записи которых содержатся только счастливые цифры 4 и 7. Например, числа 47, 744, 4 являются счастливыми, а 5, 17, 467 — не являются.

Однажды Пете встретилось дерево из n вершин. При этом дерево было взвешенным, то есть каждое его ребро имело вес (целое положительное число). Ребро счастливое, если его вес — счастливое число. Напомним, что дерево из n вершин — это неориентированный связный граф, у которого ровно n - 1 ребер.

Пете стало интересно, сколько существует таких троек вершин дерева (i, j, k), что и на пути из i в j, и на пути из i в k есть хотя бы одно счастливое ребро (все три вершины попарно различны). Порядок чисел в тройке имеет значение, то есть тройка (1, 2, 3) не равна тройке (2, 1, 3) и не равна тройке (1, 3, 2).

Найдите количество таких троек.

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

В первой строке задано единственное целое число n (1 ≤ n ≤ 105) — количество вершин дерева. В следующих n - 1 строках заданы тройки целых чисел ui vi wi (1 ≤ ui, vi ≤ n, 1 ≤ wi ≤ 109) — пара вершин, которые соединяет ребро, и его вес.

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

В единственной строке выведите одно число — ответ на задачу.

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-битных чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.

Примеры
Входные данные
4
1 2 4
3 1 2
1 4 7
Выходные данные
16
Входные данные
4
1 2 4
1 3 47
1 4 7447
Выходные данные
24
Примечание

16 троек из первого примера: (1, 2, 4), (1, 4, 2), (2, 1, 3), (2, 1, 4), (2, 3, 1), (2, 3, 4), (2, 4, 1), (2, 4, 3), (3, 2, 4), (3, 4, 2), (4, 1, 2), (4, 1, 3), (4, 2, 1), (4, 2, 3), (4, 3, 1), (4, 3, 2).

Во втором примере подходит любая тройка вершин. Всего троек: 4·3·2 = 24.