AT_arc074_c [ARC074E] RGB Sequence

有 $N$ 个格子横向排列成一行。格子从左到右依次编号为 $1$、$2$、$\ldots$、$N$。 Suknuke 君打算将每个格子涂成红色、绿色或蓝色中的一种颜色。根据 Suknuke 君的审美观，需要满足以下 $M$ 个条件。第 $i$ 个条件如下： - 第 $l_i$ 到第 $r_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 \leq N \leq 300$ - $1 \leq M \leq 300$ - $1 \leq l_i \leq r_i \leq N$ - $1 \leq x_i \leq 3$ # 样例解释 1 有如下 $6$ 种方案： - RGB - RBG - GRB - GBR - BRG - BGR 其中，R / G / B 分别表示红色、绿色、蓝色的格子。 # 样例解释 2 有如下 $6$ 种方案： - RRRG - RRRB - GGGR - GGGB - BBBR - BBBG # 样例解释 3 有 $0$ 种方案。 由 ChatGPT 5 翻译