수수께끼의 배열

$1$, $2$, ..., $N$의 순열을 담은 배열이 있다(즉, 각 수는 배열에 정확히 한 번씩 등장한다). 배열의 원소는 $1$-인덱스 방식으로 번호가 매겨진다.

하지만 배열의 내용은 알 수 없다. 대신, ``위치 $a$와 $b$ 사이의 최솟값은 무엇인가?'' 형식인 $Q$개의 질의 결과가 주어진다.

주어진 질의와 일치하는 배열의 개수를 세어야 한다.

채점

여러 하위 과제로 이루어진 테스트 세트를 통해 풀이를 채점한다. 하나의 하위 과제는 여러 테스트 케이스로 구성된다. 하위 과제의 점수를 받으려면 풀이가 해당 하위 과제에 속한 모든 테스트 케이스를 통과해야 한다.

하위 과제 | 점수 | 제한

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$

첫 번째 입력 줄에는 배열의 크기와 질의의 개수를 나타내는 두 정수 $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$개 있다.