AT_arc074_c [ARC074E] RGB Sequence

[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 $ で割った余りを出力せよ。

### 制約 - $ 1\