该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题面描述

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