시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 47 | 16 | 14 | 51.852% |
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.
3 2 1 2 2 1 3 1
2
8 3 3 7 2 6 8 2 4 5 5
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.