#H1045. Amon

Amon

题目描述

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

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

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

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

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

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

所以他决定再减弱一些难度:假定某个分身只被有且仅有一个阿蒙控制(本体不被控制),给所有阿蒙编号 1n1-n,本体为 1。

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

输入格式

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

输出格式

一个正整数,表示可能的方案个数对 109+710^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%30\% 的数据, 1n51 \le n \le 51m101 \le m \le 10
对于 100%100\% 的数据,1a,bn1 \le a, b \le n1c1091 \le c \le 10^91n3001 \le n \le 3001m1051 \le m \le 10^5