题目背景

英文题面 | 题目来源

题目描述

有一个关于人脑有趣的事实：在阅读时，它主要分析每个单词的第一个和最后一个字母，而不一定要按照正确的顺序来构造单词。因此，即使一句话基本上没有正确的单词，也可能会被正确的理解。（原文中这段文字的部分单词的字母顺序被打乱，但是译者认为这样会影响阅读，因此没有改变翻译中文字的顺序）

Elly 已经注意到，打乱某些字母会得到更好的结果！例如，字母 l 和 i、a 和 o、x 和 m 非常相似。于是她定义了一个字母的值，从 $1$ 到 $5$ 。其中，相似的字母的值较低，而非常不同的字母值较高。等号字母的值是 $1$。通过这种方式，每个单词可以被赋予一个值——相邻字母之间所有值的总和。

想象一下，她把 e 和 l 的值定义为 $3$，l 和 y 的值定义为 $2$，i 和 l 的值定义为 $1$。那么单词 elly 的值是 $3+1+2=6$（记住，等号字母的距离是 $1$）。单词 lily 的值为 $4$，而 i 的值为 $0$ =）。长单词的价值不一定比短单词大——比如 lilii（保加利亚语中lily 的复数形式）——它的值只有 $4$，但 elle（法语中的意思是 she）的价值是 $7$。但是，每增加一个字母，至少会增加一个单词的值。

Ellenora 希望构建一种即使有大量混乱的字母也很容易阅读的语言。她决定将值不大于 $N$ 的所有非空单词都包括在内。

你能帮她找出他们有多少吗？

输入格式

从标准输入读入。

第一行两个整数 $N$ 和 $M$，表示单词的值的最大值（$1\le N\le 10^9$）和字符对的数量。Elly 已经定义了一个值。所有未提及的字母对的距离都等于 $1$。接下来的 $M$ 行中的每一行都包含一个三元组 $L_1\,L_2\,F$，这意味着字母 $a\le L_1,L_2\le z$ 之间的距离为 $1\le F\le 5$。从 $L_1$ 到 $L_2$ 的距离与从 $L_2$ 到 $L_1$ 的距离相同，即距离是无序的。

输出格式

输出到标准输出。

一行，一个整数，表示由小写英文字母组成的单词数，满足它的值不大于 $N$。因为这个数量可能非常大，所以你只需要输出它对 $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

提示

数据范围

对于 $50\%$ 的数据，$N\le 10^6$。

对于全部数据，$1\le N\le 10^9$，每一对字母最多只会出现一次。

样例解释

一些可行的单词有：elleonora、entwine、aaaaaaaaaaaaaaaaaaaaa。