题目背景

译自 Nordic Olympiad in Informatics 2018 Mysterious Array。

题目描述

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

然而，你并不知道数组的具体内容。你会得到 $Q$ 条信息，信息的形式是“在编号 $a$ 和 $b$ 之间的最小值是多少”。

你的任务是计算出符合这些查询的数组的数量。

输入格式

输入的第一行包含两个整数 $N$ 和 $Q$（$1\leq N,Q$）：数组的大小和条件的数量。

接下来有 $Q$ 行描述信息。每行包含三个整数 $a$、$b$ 和 $x$（$1 \leq a \leq b \leq N$ 且 $1 \leq x \leq N$）：表示在位置 $a$ 和 $b$ 之间的最小值为 $x$。

注意，查询的结果可能不一致，并且有可能不存在符合这些查询的数组。

输出格式

输出一个整数：数组的数量对 $10^9 + 7$ 取模的结果。

3 2
1 2 2
1 3 1

2

8 3
3 7 2
6 8 2
4 5 5

576

提示

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

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

你的解法将在一组子任务上进行评分。每个子任务包含多个测试用例。要获得子任务的分数，你的解法必须通过子任务中的所有测试用例。