题目描述

Petya 喜欢幸运数字。众所周知，幸运数是十进制表示中只含幸运数字 4 和 7 的正整数。例如 47、744、4 是幸运数，而 5、17、467 不是。

一天，Petya 遇到了一棵有 $n$ 个顶点的树。这棵树还带权：每条树边都有一个权值（正整数）。若一条边的权值是幸运数，则称这条边是幸运边。注意，$n$ 个顶点的树是一个恰有 $n-1$ 条边的无向连通图。

Petya 想知道有多少个顶点三元组 $(i, j, k)$ 满足：从 $i$ 到 $j$ 的路径上以及从 $i$ 到 $k$ 的路径上都至少有一条幸运边（三个顶点两两不同）。三元组中数字的顺序是有讲究的：$(1,2,3)$ 不等于 $(2,1,3)$，也不等于 $(1,3,2)$。

求这样的顶点三元组有多少个。

输入格式

第一行包含一个整数 $n$（$1 \le n \le 10^5$），表示树的顶点数。接下来 $n-1$ 行，每行三个整数 $u_i$、$v_i$、$w_i$（$1 \le u_i, v_i \le n$，$1 \le w_i \le 10^9$），表示一条边连接的两个顶点及该边的权值。

输出格式

输出一行一个数，即答案。

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 \cdot 3 \cdot 2 = 24$。