시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 2 2 1 100.000%

문제

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.

입력

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 ≤ a ≤ b ≤ N and 1 ≤ x ≤ 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.

출력

Print one integer: the number of arrays modulo 109 + 7.

서브태스크 1 (23점)

  • 1 ≤ N, Q ≤ 10

서브태스크 2 (35점)

  • 1 ≤ N, Q ≤ 1000

서브태스크 3 (42점)

  • 1 ≤ N, Q ≤ 2 · 105

예제 입력 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

힌트

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.