题目描述

题目译自 NordicOI 2018 T3 「Mysterious Array」

有一个数组，包含数字 $1$ 到 $N$ 的一个排列（即每个数字在数组中恰好出现一次）。数组的元素是从 $1$ 开始编号的。

不过，你并不知道数组的具体内容。相反，你得到了 $Q$ 个查询的结果，每个查询的形式是「位置 $a$ 到 $b$ 之间的最小值是多少？」

你的任务是计算有多少个数组符合这些查询条件。

输入格式

第一行输入包含两个整数 $N$ 和 $Q$，表示数组的大小和查询的数量。

接下来有 $Q$ 行，每行包含三个整数 $a, b, x$ $(1 \le a \le b \le N, 1 \le x \le N)$，表示位置 $a$ 到 $b$ 之间的最小值是 $x$。

注意，查询结果可能不一致，可能没有任何数组符合这些条件。

输出格式

输出一个整数，表示符合查询条件的数组数量，结果对 $10^9+7$ 取模。

3 2
1 2 2
1 3 1

2

在第一个样例中，有一个大小为 3 的数组，包含数字 $1$、$2$ 和 $3$ 的排列。此外，给出了位置 $1$ 到 $2$ 之间的最小值是 $2$，以及位置 $1$ 到 $3$ 之间（即整个数组）的最小值是 $1$。只有两个数组符合这些条件：$[2,3,1]$ 和 $[3,2,1]$。

8 3
3 7 2
6 8 2
4 5 5

576

在第二个样例中，有 $576$ 个数组符合给定的条件。

数据范围与提示

详细子任务附加限制及分值如下表所示。