Problem C
Mysterious Array

There is an array that contains a permutation of the numbers $1$, $2$, …, $N$ (i.e., each number appears exactly once in the array). The elements of the array are $1$-indexed.

However, you don’t know the contents of the array. Instead, you are given the results of $Q$ queries of the form “what is the minimum value between positions $a$ and $b$?”

Your task is to count the number of arrays that match the queries.

Input

The first input line contains two integers $N$ and $Q$: the size of the array and the number of queries.

Then there are $Q$ lines that describe the queries. Each line contains three integers $a$, $b$, and $x$ ($1 \le a \le b \le N$ and $1 \le x \le N$): the minimum value between positions $a$ and $b$ is $x$.

Note that the results of the queries might be inconsistent, and it is possible that no array matches them.

Output

Print one integer: the number of arrays modulo $10^9+7$.

Grading

Your solution will be graded on a set of subtasks. A subtask will consist of multiple test cases. To get the points for a subtask, your solution must pass all test cases that are part of the subtask.

Explanation of examples

In the first example there is an array of size $3$, containing a permutation of the numbers $1$, $2$ and $3$. Additionally, it is given that the minimum among the numbers at indices between $1$ and $2$ is $2$, and the minimum among the numbers at indices between $1$ and $3$ (i.e. the whole array) is $1$. There are only two arrays matching these conditions: $[2,3,1]$ and $[3,2,1]$.

In the second example there are $576$ arrays that match the given conditions.

3 2
1 2 2
1 3 1

2

8 3
3 7 2
6 8 2
4 5 5

576