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，则问总共可形成多少符合条件的单词？

Format

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

Samples

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

470059518