Background

English statement | Source

Problem Description

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$.

Input Format

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.

Output Format

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$.

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

Hint

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