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

题面描述

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