题目描述

有 $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

输入

3 1
1 3 3

输出

6

样例 2

输入

4 2
1 3 1
2 4 2

输出

6

样例 3

输入

1 3
1 1 1
1 1 2
1 1 3

输出

0

样例 4

输入

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 \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 翻译