읽기

사람의 뇌에는 흥미로운 특징이 있다. 글을 읽을 때 뇌는 주로 각 단어의 첫 글자와 마지막 글자만 정확히 보고 나머지는 알아서 채워 넣는다. 그래서 가운데 글자들의 순서가 뒤섞인 문장도 거의 힘들이지 않고 읽을 수 있다.

Elly는 어떤 뒤섞임은 다른 것보다 더 잘 읽힌다는 사실을 알아차렸다. 예를 들어 l과 i, 또는 a와 o는 x와 m보다 훨씬 비슷해 보인다. 그래서 Elly는 두 글자 사이의 차이를 $1$부터 $5$까지의 값으로 매긴다. 비슷한 글자일수록 값이 작고, 많이 다를수록 값이 크다. 같은 글자 두 개의 차이는 항상 $1$이다.

단어의 값은 인접한 글자 쌍마다의 차이를 모두 더한 값이다. 예를 들어 e와 l의 차이가 $3$, l과 y의 차이가 $2$, i와 l의 차이가 $1$이라면, 단어 elly의 값은 $3 + 1 + 2 = 6$이다(같은 글자 쌍 l-l은 $1$을 더한다는 점을 기억하라). 같은 차이 값에서 단어 lily의 값은 $4$이고, i처럼 한 글자짜리 단어의 값은 $0$이다.

긴 단어가 항상 짧은 단어보다 값이 큰 것은 아니다. lilii의 값은 $4$에 불과하지만 elle의 값은 $7$이다. 다만 글자를 하나 더 붙일 때마다 값은 최소 $1$ 이상 늘어난다.

Elly는 글자가 많이 뒤섞여도 쉽게 읽을 수 있는 언어를 만들고 싶어서, 값이 $N$ 이하인 비어 있지 않은 모든 단어를 포함하려고 한다. 그런 단어가 몇 개인지 세어 Elly를 도와주자.

첫 번째 줄에 두 정수 $N$과 $M$이 주어진다. $N$은 허용되는 단어 값의 최댓값이고($1 \le N \le 10^9$), $M$은 차이가 정의된 글자 쌍의 개수이다.

이어지는 $M$개의 줄에는 각각 L1 L2 F가 주어지며, 이는 소문자 $L1$과 $L2$의 차이가 $F$임을 뜻한다($1 \le F \le 5$). 차이는 대칭이므로 $L1$에서 $L2$로의 차이와 $L2$에서 $L1$로의 차이는 같다. 목록에 없는 모든 쌍의 차이는 $1$이다.

소문자 알파벳으로 이루어진 단어 중 값이 $N$ 이하인 비어 있지 않은 단어의 개수를 정수 하나로 출력하라. 이 값은 매우 커질 수 있으므로 $10^9 + 7$로 나눈 나머지를 출력한다.

재미로 덧붙이면, 조건을 만족하는 단어로는 elleonora, entwine, aaaaaaaaaaaaaaaaaaaaa 등이 있다.