[BalkanOI2009] Reading

[英文题面](/problem/U126973) | [题目来源](http://www.cs.org.mk/boi2009/tasks.html)

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