---

题目描述

题目译自 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$ 取模。

---

样例 1

输入

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]$。

---

样例 2

输入

8 3
3 7 2
6 8 2
4 5 5

输出

576

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

---

数据范围与提示

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

子任务	分值	附加限制
1	23	$1 \leq N,Q \leq 10$
2	35	$1 \leq N,Q \leq 1000$
3	42	$1 \leq N,Q \leq 2\cdot 10^5$

---