题目描述

有一个长度为 $N$ 的数组，它是 $1,2,\dots,N$ 的一个排列，也就是说每个数恰好出现一次。数组下标从 $1$ 开始。

但是你并不知道这个数组的具体内容。现在给出 $Q$ 个询问结果，每个询问形如：区间 $[a,b]$ 中的最小值是 $x$。

你的任务是计算有多少个排列满足所有给定的询问结果。

注意，给出的询问结果可能互相矛盾，因此满足条件的排列数量可能为 $0$。

输入格式

第一行包含两个整数 $N,Q$，表示数组长度和询问数量。

接下来 $Q$ 行，每行三个整数 $a,b,x$，表示区间 $[a,b]$ 中的最小值为 $x$。

输出格式

输出一个整数，表示满足所有询问结果的排列数量，对 $10^9+7$ 取模。

样例 1 输入

3 2
1 2 2
1 3 1

样例 1 输出

2

样例 1 解释

长度为 $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

样例 2 输出

576

数据范围与子任务

• $1 \le a \le b \le N$
• $1 \le x \le N$