Petya 喜欢幸运数字。我们都知道,幸运数字是十进制表示中仅包含幸运数字4和7的正整数。例如,数字47、744、4是幸运数字,而5、17、467则不是幸运数字。
有一天,Petya 遇到了一棵有 n 个顶点的树。此外,这棵树是加权的,即。 e.树的每条边都有权重(正整数)。如果一条边的权重是一个幸运数字,那么它就是幸运的。请注意,具有 n 个顶点的树是恰好具有 n - 1 条边的无向连通图。
Petya 想知道从 i 到 j 的路上以及从 i 到 k 的路上必须至少有一个幸运边(所有三个顶点都是成对不同的),存在多少个顶点三元组 (i, j, 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 说明符。
示例
输入 #1
4 1 2 4 3 1 2 1 4 7
输出 #1
16
输入 #2
4 1 2 4 1 3 47 1 4 7447
输出 #2
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。