题目描述

拨弄时光的指针，遨游命运的影子，欺诈与恶作剧的化身，伟大的错误先生。——赞美阿蒙！

“你杀了我吧。”——克莱恩·莫雷蒂

小克被阿蒙拐进神弃之地后一直尝试逃离，但是阿蒙擅长使用分身欺诈，小克无法摸清它们的关系。

现在阿蒙给了他一些逃跑的机会，小克开始猜测：

假定阿蒙与祂的分身们存在一些控制关系，即某个阿蒙可能控制另一个阿蒙，且控制方法可能有多种。现在他需要知道总共有多少种控制的情况。

他发现这个问题十分无解，毕竟阿蒙的分身亿亿万，彼此之间也没有什么区别。

所以他决定再减弱一些难度：假定某个分身只被有且仅有一个阿蒙控制（本体不被控制），给所有阿蒙编号 $1-n$，本体为 1。

你作为伟大的“愚者”的信徒，虽然现在祂没有回应你们的祈祷，但小克仍然希望知道所有可能的方案个数。

输入格式

第一行两个整数 $n,m$，分别表示阿蒙数与可能的关系数。
第二到 $m + 1$ 行，每行三个正整数 $a,b,c$，表示阿蒙 $a$ 可能控制阿蒙 $b$，控制的方法数为 $c$。

输出格式

一个正整数，表示可能的方案个数对 $10^9 +7$ 取模的结果。

5 9
1 2 3
3 2 1
1 3 1
2 4 2
3 5 1
4 3 4
3 5 1
5 4 1
4 4 6

72

数据范围与提示

对于 $30\%$ 的数据， $1 \le n \le 5$，$1 \le m \le 10$。
对于 $100\%$ 的数据，$1 \le a, b \le n$，$1 \le c \le 10^9$，$1 \le n \le 300$，$1 \le m \le 10^5$。