Reading

A curious fact about the human brain is that, when we read, it mostly looks at the first and last letter of each word and fills in the rest — so a sentence whose inner letters are shuffled can still be read almost effortlessly.

Elly noticed that some shuffles read better than others: the letters l and i, or a and o, look much more alike than, say, x and m. She rates the difference between two letters on a scale from $1$ to $5$ — similar letters get a low value, very different letters a high one. Two equal letters always have difference $1$.

The value of a word is the sum of the differences between every pair of adjacent letters. For example, if the difference between e and l is $3$, between l and y is $2$, and between i and l is $1$, then the word elly has value $3 + 1 + 2 = 6$ (recall that the equal pair l-l contributes $1$). With those same differences the word lily has value $4$, and a single letter such as i has value $0$.

A longer word is not always worth more than a shorter one: lilii has value only $4$, while elle has value $7$. Still, every extra letter adds at least $1$ to a word's value.

Elly wants to design a language that stays easy to read even with many misplaced letters, so she will include every non-empty word whose value is at most $N$. Help her by counting how many such words there are.

The first line contains two integers $N$ and $M$ — the largest allowed word value ($1 \le N \le 10^9$) and the number of letter pairs for which a difference is defined.

Each of the next $M$ lines contains L1 L2 F, meaning the difference between the lowercase letters $L1$ and $L2$ is $F$ ($1 \le F \le 5$). The difference is symmetric, so it is the same from $L1$ to $L2$ and from $L2$ to $L1$. Every pair not listed has difference $1$.

Print a single integer — the number of non-empty words made of lowercase English letters whose value is at most $N$. Because this count can be enormous, print it modulo $10^9 + 7$.

As a bit of trivia, elleonora, entwine, and aaaaaaaaaaaaaaaaaaaaa are among the words that satisfy the condition.