접미사 배열 3

문자열 $S$의 $i$번째 접미사는 $S$의 $i$번째 글자에서 시작하는 접미사(suffix)다. 예를 들어 $S$ = "abcde"이면 1번째 접미사는 "abcde", 4번째 접미사는 "de"다.

$S$의 접미사 배열은 $S$의 모든 접미사를 사전 순으로 정렬한 배열이다. 배열에 들어가는 값은 접미사 번호이고, 정렬은 그 번호에 해당하는 접미사로 한다. 예를 들어 $S$ = "abca"이면 접미사 배열은 (4, 1, 2, 3)이다.

길이가 $N$인 접미사 배열이 주어졌을 때, 그 접미사 배열을 만드는 문자열 $S$의 개수를 구하는 프로그램을 작성하시오.

$N$이 매우 크므로 접미사 배열 $SA$는 다음 연산으로 만든다. 먼저 SA[i] = i로 초기화하고, 이어서 $M$개의 연산을 주어진 순서대로 적용한다. 위치는 모두 1번부터 센다.

• 0 u v: $SA$의 $u$번째부터 $v$번째까지를 배열의 가장 앞으로 옮긴다. 이 연산을 적용한 후의 접미사 배열은 SA[u], SA[u+1], ..., SA[v], SA[1], SA[2], ..., SA[u-1], SA[v+1], ..., SA[N]이다.
• 1 u v: $SA$의 $u$번째부터 $v$번째까지를 뒤집는다. 이 연산을 적용한 후의 접미사 배열은 SA[1], SA[2], ..., SA[u-1], SA[v], SA[v-1], ..., SA[u+1], SA[u], SA[v+1], ..., SA[N]이다.

이 문제에서 문자열은 양의 정수로 이루어진 배열이다. 문자열에 포함된 서로 다른 정수의 개수는 문자열에 포함된 가장 큰 정수와 같아야 한다. 예를 들어 (1, 2, 2)와 (4, 5, 1, 2, 3)은 올바른 문자열이지만, (1, 1, 3)과 (-1, 0, 1, 2)는 올바른 문자열이 아니다.

첫째 줄에 문자열의 길이 $N$ ($1 \le N \le 10^9$)과 연산의 개수 $M$ ($0 \le M \le 10^5$)이 주어진다. 둘째 줄부터 $M$개의 줄에 접미사 배열을 만드는 연산이 한 줄에 하나씩 주어진다. 모든 연산은 $1 \le u \le v \le N$을 만족한다.

입력으로 주어진 접미사 배열 $SA$를 만드는 문자열 $S$의 개수를 $10^9+7$로 나눈 나머지를 출력한다.

첫 번째 예제에서 접미사 배열은 처음에 (1, 2, 3, 4)다. 첫 연산을 적용하면 (1, 3, 2, 4)가 되고, 두 번째 연산까지 적용하면 (2, 4, 1, 3)이 된다. 가능한 문자열은 (2, 1, 2, 2), (2, 1, 3, 2), (3, 1, 3, 2), (3, 1, 4, 2)다.