P6841 [BalkanOI 2009] Reading

[English statement](/problem/U126973) | [Source](http://www.cs.org.mk/boi2009/tasks.html)

There is an interesting fact about the human brain: when reading, it mainly looks at the first and last letter of each word, and it does not necessarily need the letters inside to be in the correct order to recognize the word. Therefore, even if a sentence has almost no words spelled correctly, it may still be understood correctly. (In the original text, some words in this paragraph have their letters shuffled, but the translator believes this would affect readability, so the order of letters in the translated text is kept unchanged.) Elly has noticed that shuffling certain letters can give even better results. For example, the letters `l` and `i`, `a` and `o`, `x` and `m` look very similar. So she defines a value for a pair of letters, from $1$ to $5$. Similar letters have a smaller value, and very different letters have a larger value. The value for equal letters is $1$. In this way, each word can be assigned a value—the sum of the values of all adjacent letter pairs. Imagine she defines the value between `e` and `l` as $3$, between `l` and `y` as $2$, and between `i` and `l` as $1$. Then the value of the word `elly` is $3+1+2=6$ (remember that the distance between equal adjacent letters is $1$). The value of the word `lily` is $4$, while the value of `i` is $0$. Long words do not necessarily have a larger value than short words—for example, `lilii` (the plural form of `lily` in Bulgarian) has value only $4$, but `elle` (meaning `she` in French) has value $7$. However, each time you add one letter, the value of the word increases by at least $1$. Ellenora wants to design a language that is easy to read even with lots of scrambled letters. Find the number of all non-empty words whose value is not greater than $N$.

Read from standard input. The first line contains two integers $N$ and $M$, representing the maximum allowed word value ($1\le N\le 10^9$) and the number of given letter pairs. Elly has defined a value for these pairs. For all letter pairs not mentioned, the distance is $1$. Each of the next $M$ lines contains a triple $L_1\,L_2\,F$, meaning the distance between the letters $a\le L_1,L_2\le z$ is $1\le F\le 5$. The distance from $L_1$ to $L_2$ is the same as from $L_2$ to $L_1$, i.e. the distance is unordered.

Write to standard output. Output one integer: the number of words consisting of lowercase English letters whose value is not greater than $N$. Since this number can be very large, output it modulo $10^9+7$.

**Constraints** For $50\%$ of the testdata, $N\le 10^6$. For all testdata, $1\le N\le 10^9$, and each unordered pair of letters appears at most once. --- **Sample Explanation** Some valid words are: `elleonora`, `entwine`, `aaaaaaaaaaaaaaaaaaaaa`. Translated by ChatGPT 5