题目描述

你有一个有重边、自环的无向图，每条边有个计数器，对各自的 $c_i$ 取模。

对于任何一条图上可经过重边、自环的路径（起点、终点均任意），每条边经过次数对 $c_i$ 取模得到一个数组（长度为边数 $m$）。你想知道这样的数组共有多少种可以由一条路径生成。答案对 $10^9+7$ 取模。

输入格式

一行两个整数 $n,m$。

接下来 $m$ 行，每行三个整数 $u,v,c$，描述一条 $u,v$ 之间的无向边，它的计数器对 $c$ 取模。

输出格式

一行一个整数表示答案。

样例输入

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

样例输出

27

数据范围

本题设有subtask。

对于全部数据，$1\leq n,m\leq 3\cdot 10^5,1\leq c_i\leq 10^9$。

subtask1(30)，$n,m\leq 3000$

subtask2(20)，输入为一棵联通的树，满足 $m=n-1$

subtask3(20)，所有 $c_i$ 均为偶数。

subtask4(30)，无特殊限制。