Migrated from Lutece 2794 大衍

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

“大衍之数五十，其用四十有九。分而为二以象两，挂一以象三， 揲之以四以象四时，归奇于扐以象闰，五岁再闰，故再扐而后挂。 天一地二，天三地四，天五地六，天七地八，天九地十。天数五，地数五，五位相得而各有合。天数二十有五，地数三十，凡天地之数五十有五。此所以成变化而行鬼神也。” ----《周易.系辞上》

YL 最近在学习易经，他发现大衍之数和两个质数 $2,5$ 关系密切，他尝试利用卜算进行推演。

具体的，YL 有一个长度为 $n$ 的序列，下标从 $0$ 开始，每个位置都是一个 $[0,9]$ 范围内的整数，他尝试对这个序列进行了 $q$ 次推演，每次推演得到信息为：区间 $[l,r]$ 的积模 $10$ 的余数为 $x$。现在他想根据推演的结果求出可能的序列。由于太多了，所以他只想知道可能的序列数对 $10^9+7$ 取模的结果。

Input

第一行输入两个整数 $n,q$。 接下来 $q$ 行每行三个整数 $l,r,x$。

Output

输出一个整数表示答案对 $10^9+7$ 取模的结果

Samples

3 2
0 1 5
1 2 8

4

5 3
0 1 3
2 4 4
0 4 6

0

8 4
2 3 2
0 7 0
3 4 6
6 6 7

118080

Constraints

$1\le n\le 100$ $1\le q\le 50$

Resources

2022 UESTC ICPC Training for Dynamic Programming