Suffix Array 3

The $i$-th suffix of a string $S$ is the suffix that starts at the $i$-th character of $S$. For example, if $S$ = "abcde", the 1st suffix is "abcde" and the 4th suffix is "de".

The suffix array of $S$ lists every suffix of $S$ in lexicographic order. Each entry of the array is a suffix number, and the sorting compares the suffixes those numbers refer to. For example, if $S$ = "abca", the suffix array is (4, 1, 2, 3).

Given a suffix array of length $N$, write a program that counts the strings $S$ whose suffix array is that array.

Because $N$ can be very large, the suffix array $SA$ is built by operations. First initialize SA[i] = i, then apply $M$ operations in the given order. All positions are counted from 1.

• 0 u v: move the $u$-th through $v$-th entries of $SA$ to the front of the array. After this operation the suffix array is SA[u], SA[u+1], ..., SA[v], SA[1], SA[2], ..., SA[u-1], SA[v+1], ..., SA[N].
• 1 u v: reverse the $u$-th through $v$-th entries of $SA$. After this operation the suffix array is SA[1], SA[2], ..., SA[u-1], SA[v], SA[v-1], ..., SA[u+1], SA[u], SA[v+1], ..., SA[N].

In this problem a string is an array of positive integers. The number of distinct integers in the string must equal the largest integer in the string. For example, (1, 2, 2) and (4, 5, 1, 2, 3) are valid strings, while (1, 1, 3) and (-1, 0, 1, 2) are not.

The first line contains the length of the string $N$ ($1 \le N \le 10^9$) and the number of operations $M$ ($0 \le M \le 10^5$). Each of the next $M$ lines contains one operation that builds the suffix array. Every operation satisfies $1 \le u \le v \le N$.

Print the number of strings $S$ whose suffix array is the $SA$ given in the input, modulo $10^9+7$.

In the first example the suffix array starts as (1, 2, 3, 4). After the first operation it is (1, 3, 2, 4), and after the second operation it is (2, 4, 1, 3). The possible strings are (2, 1, 2, 2), (2, 1, 3, 2), (3, 1, 3, 2), (3, 1, 4, 2).