序列
题面描述
绿绵羊在基♂房找到了个序列\(a\),长度为\(n\)。现将其用红黄蓝三色涂色,满足以下要求:
- 对于所有的\(1 \leq i \leq m\)从\(a_{l_i}\)至\(a_{r_i}\)中有\(x_i\)种颜色。
问总共有多少种符合以上条件的\(a\)?将答案对\(10^9+7\)取模。
输入格式
\(n\) \(m\)
\(l_1\) \(r_1\) \(x_1\)
\(l_2\) \(r_2\) \(x_2\)
\(......\)
\(l_m\) \(r_m\) \(x_m\)
输出格式
输出符合要求的\(a\)的数量,对\(10^9+7\)取模。
样例输入
8 10
2 6 2
5 5 1
3 5 2
4 7 3
4 4 1
2 3 1
7 7 1
1 5 2
1 7 3
3 4 2
样例输出
108
说明
\(m \leq n \leq 300\)