有一个包含数字 $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$ 取模。

子任务

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

说明

在第一个样例中，有一个大小为 $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