/ MYOJ / 题库 /

序列

序列

题面描述

绿绵羊在基♂房找到了个序列\(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\)

信息

ID
1056
难度
9
分类
(无)
标签
递交数
15
已通过
1
通过率
7%
上传者

相关

在下列比赛中:

MOI 2021