题目描述
有一个数组,包含了 $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$ 取模的结果。
样例输入 #1
3 2
1 2 2
1 3 1
样例输入 #2
8 3
3 7 2
6 8 2
4 5 5
提示
在第一个样例中,数组的大小是 $3$,包含了数 $1$、$2$ 和 $3$ 的一个排列。此外,给定了以下信息:编号 $1$ 到 $2$ 之间的最小值是 $2$,编号 $1$ 到 $3$ 之间(即整个数组)的最小值是 $1$。只有两个数组符合这些条件:$[2, 3, 1]$ 和 $[3, 2, 1]$。
在第二个样例中,有 $576$ 个数组符合给定的条件。
对所有数据,$1\leq N,Q\leq 2\cdot 10^5$。