题目描述

$N$ 個のマスが横一列に並んでいます。 マスには左から順に $1$, $2$, $...$, $N$ と番号が振られています。

すぬけ君は、各マスを 赤 / 緑 / 青 のどれかの色で塗ろうとしています。 すぬけ君の美的感覚によると、次の $M$ 個の条件がすべて成り立つ必要があるそうです。 $i$ 番目の条件は次のようなものです。

• マス $l_i$, $l_i\ +\ 1$, $...$, $r_i$ の色の種類数がちょうど $x_i$ である。

条件がすべて成り立つようなマスの配色は何通りでしょうか？ $10^9+7$ で割った余りを求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

条件がすべて成り立つようなマスの配色は何通りか？ $10^9+7$ で割った余りを出力せよ。

题目大意

有一个序列$\left\{a_{N}\right\}$，要给序列中的每个元素一种颜色：红/绿/蓝。有$M$条限制$(l,r,x)$，表示格子$l$~$r$中颜色的种数要恰好为$x$，问可行的方案数。

3 1
1 3 3

6

4 2
1 3 1
2 4 2

6

1 3
1 1 1
1 1 2
1 1 3

0

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

提示

制約

• $1\ <\ =\ N\ <\ =\ 300$
• $1\ <\ =\ M\ <\ =\ 300$
• $1\ <\ =\ l_i\ <\ =\ r_i\ <\ =\ N$
• $1\ <\ =\ x_i\ <\ =\ 3$

Sample Explanation 1

次の $6$ 通りです。 - RGB - RBG - GRB - GBR - BRG - BGR ただし、R / G / B はそれぞれ 赤 / 緑 / 青 のマスを表します。

Sample Explanation 2

次の $6$ 通りです。 - RRRG - RRRB - GGGR - GGGB - BBBR - BBBG

Sample Explanation 3

次の $0$ 通りです。