[ARC074E] RGB Sequence

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

[problemUrl]: https://atcoder.jp/contests/arc074/tasks/arc074_c $ 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 $ で割った余りを出力せよ。

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 $ 通りです。