题目描述

有$N$个正方形排成一行。这些正方形从左到右依次编号为$1$, $2$, $...$, $N$。

Snuke将每个正方形涂成红色、绿色或蓝色。根据他的审美观，下面的$M$个条件必须全部满足。第$i$个条件是：

• 在正方形$l_i$, $l_i + 1$, $...$, $r_i$之间，恰好有$x_i$种不同的颜色。

有多少种方式可以涂色以满足所有的条件？计算结果对$10^9+7$取模。

约束条件

• $1 ≤ N ≤ 300$
• $1 ≤ M ≤ 300$
• $1 ≤ l_i ≤ r_i ≤ N$
• $1 ≤ x_i ≤ 3$

输入

输入以以下格式从标准输入中给出：

$N$ $M$ $l_1$ $r_1$ $x_1$ $l_2$ $r_2$ $x_2$ $:$ $l_M$ $r_M$ $x_M$

输出

打印满足所有条件的涂色方式的数量，对$10^9+7$取模。

示例输入1

3 1
1 3 3

示例输出1

6

六种涂色方式是：

• RGB
• RBG
• GRB
• GBR
• BRG
• BGR

这里，R、G和B分别代表红色、绿色和蓝色的正方形。

示例输入2

4 2
1 3 1
2 4 2

示例输出2

6

六种涂色方式是：

• RRRG
• RRRB
• GGGR
• GGGB
• BBBR
• BBBG

示例输入3

1 3
1 1 1
1 1 2
1 1 3

示例输出3

0

没有任何一种涂色方式满足条件。

示例输入4

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

示例输出4

108