UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#2983. [Balkan2009]reading

Statistics 下载数据

Description

定义任意两小写字母间有一个差别值X(1<=X<=5),假设26个小写字母随意排列构成的都是单词,则对于一个单词可算出差别总和为sum,例如:
假设X[e-l]=3,X[l-y]=2,X[l-l]=1,则单词“elly”的sum值为3+1+2=6。
现在给出N和M,N表示sum值的上限(可以等于N),M表示已知关系个数,接下来M行,每行三个数L1,L2,F,表示字母L1到L2和L2到L1的X值都为F,若未提及的字母对则默认它们的X值为1,则问总共可形成多少符合条件的单词?
 

Input

第一行N,M (1<=N<=1000 000 000)
之后M行,每行三个数L1,L2,F,保证每对字母最多出现一次。
 

Output

 
   符合条件的单词总数 mod 1000 000 007 的结果。
 
数据范围
   50% N<=1000 000
100% N<=1000 000 000   1<=F<=5
 

Sample Input

20 10
e l 3
e o 1
o n 2
o r 4
r a 4
i n 5
e n 2
n t 3
t w 3
w i 5

Sample Output

470059518

Hint

Source