给定一个包含 $n$ 个顶点和 $m$ 条边的无向图 $G$。图中允许存在自环和重边。每条边 $i$ 被赋予一个正整数 $a_i$，并设有一个初始值为零的计数器 $b_i$。

考虑该图上的以下过程：我们任意选择起始顶点 $v_1$，然后沿着某条边 $e_1$ 从 $v_1$ 走到 $v_2$，接着沿着某条边 $e_2$ 从 $v_2$ 走到 $v_3$，以此类推。换句话说，我们在图中走过一条路径，该路径可能多次经过某些边和顶点。每当我们以任意方向经过边 $i$ 时，其计数器 $b_i$ 变为 $(b_i + 1) \pmod{a_i}$。我们可以在任意步数（包括零步）后停止该过程。

我们将该过程结束后的数组 $(b_1, b_2, \dots, b_m)$ 称为配置数组。考虑对应于图中所有可能的有限路径的所有过程，它们能产生多少种不同的配置数组？如果两个配置数组至少有一个元素不同，则认为它们是不同的。由于答案可能非常大，请输出其对 $10^9 + 7$ 取模的结果。

输入格式

第一行包含两个由空格分隔的整数 $n, m$ ($1 \le n \le 2 \cdot 10^5, 0 \le m \le 4 \cdot 10^5$)，分别表示图的顶点数和边数。

接下来的 $m$ 行包含边的描述，每行描述一条边：第 $i$ 条边由三个整数 $u_i, v_i, a_i$ ($1 \le u_i, v_i \le n, 1 \le a_i \le 10^9$) 描述，分别表示边的两个端点以及分配给该边的数值。

顶点编号从 1 开始。

注意，图中允许存在自环和重边。

输出格式

输出一行，表示不同配置数组的数量对 $10^9 + 7$ 取模的结果。

样例

样例输入 1

5 5
1 2 2
2 3 2
3 4 2
4 5 2
5 1 1

样例输出 1

14