配点 : $800$ 点

問題文

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

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

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

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

制約

• $1 \leq N \leq 300$
• $1 \leq M \leq 300$
• $1 \leq l_i \leq r_i \leq N$
• $1 \leq x_i \leq 3$

入力

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

$N$ $M$

$l_1$ $r_1$ $x_1$

$l_2$ $r_2$ $x_2$

$:$

$l_M$ $r_M$ $x_M$

出力

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

3 1
1 3 3

6

次の $6$ 通りです。

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

ただし、R / G / B はそれぞれ 赤 / 緑 / 青 のマスを表します。

4 2
1 3 1
2 4 2

6

次の $6$ 通りです。

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

1 3
1 1 1
1 1 2
1 1 3

0

次の $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