P11505 [NordicOI 2018] Mysterious Array

译自 Nordic Olympiad in Informatics 2018 [Mysterious Array](https://noi18.kattis.com/contests/noi18/problems/mysterious)。

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