有一个包含数字 $1, 2, \dots, 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 | 23 | $1 \le N, Q \le 10$ |
| 2 | 35 | $1 \le N, Q \le 1000$ |
| 3 | 42 | $1 \le N, Q \le 2 \cdot 10^5$ |
说明
在第一个样例中，有一个大小为 $3$ 的数组，包含 $1, 2, 3$ 的排列。此外，已知位置 $1$ 到 $2$ 之间的最小值为 $2$，位置 $1$ 到 $3$（即整个数组）之间的最小值为 $1$。只有两个数组符合这些条件：$[2, 3, 1]$ 和 $[3, 2, 1]$。
在第二个样例中，有 $576$ 个数组符合给定的条件。
样例
样例输入 1
3 2 1 2 2 1 3 1
样例输出 1
2
样例输入 2
8 3 3 7 2 6 8 2 4 5 5
样例输出 2
576