Permutation Restoration with Minimum Queries

You are given a permutation of the integers \(1\) to \(N\) stored in a 1-indexed array, but the content of the array is hidden. You will receive \(Q\) queries; each query is given in the form:

\(a\ b\ m\)

which means that the minimum element in the subarray from index \(a\) to index \(b\) (both inclusive) is exactly \(m\). In other words, for each query with parameters \(a\), \(b\) and \(m\), the following conditions must hold:

• For every index \(i\) with \(a \le i \le b\), the value \(X_i \ge m\).
• At least one index \(i\) in the range \([a,b]\) has \(X_i = m\).

Your task is to count the number of permutations that are consistent with all the queries. Since the answer can be large, output it modulo \(10^9+7\).

inputFormat

The first line contains two integers \(N\) and \(Q\) \( (1 \le N \le \text{small},\; 0 \le Q \le \text{small})\), representing the size of the permutation and the number of queries.

Each of the next \(Q\) lines contains three integers \(a\), \(b\), and \(m\) \( (1 \le a \le b \le N,\; 1 \le m \le N)\). Each query means that the minimum value in the subarray from index \(a\) to index \(b\) must be exactly \(m\).

You may assume that the queries are such that the answer fits in a 32-bit signed integer after taking the modulo.

outputFormat

Output a single integer: the number of permutations satisfying all the given queries, modulo \(10^9+7\).

sample

3 2
1 2 1
2 3 2

2