Very Long Suffix Array

All submissions for this problem are available.
Let S = s_{1}, s_{2}, ...,s_{n} be a string and let S[i, j] denote the substring s_{i}, s_{i+1}, ... s_{j}. The suffix array A of S is an array of integers giving the starting positions of suffixes of S in lexicographical order. This means, the entry A[i] contains the starting position of the ith smallest(lexicographically) suffix of S. In other words, for all 1 < i ≤ n: S[A[i  1], n] < S[A[i], n].
Let us take an example. Suppose S = "12323". Then all suffixes of S are "12323", "2323", "323", "23", "3". If we sort the suffixes lexicographically, we get "12323", "23", "2323", "3", "323". Therefore the suffix array, which gives the starting positions of suffixes in lexicographic order, will be A = 1, 4, 2, 5, 3.
There is exactly one suffix array for each string. However, several strings can give the same suffix array. In this problem, given a suffix array A of length N, you have to calculate the number of strings S whose suffix array is A.
However, N can be very large, so the array A is not given directly. You should initialize the array A as A[i] = i for all 1 ≤ i ≤ N and apply M operations to it in order to obtain the desired suffix array A. Each operation can be of one of the following types:
 0 u v: Remove the subsequence A[u,v] and bring it to the front. After this operation, the N elements would be in the following order:
A[u], A[u + 1], ...
A[v], A[1], A[2], ... A[u  1], A[v + 1], A[v + 2], ... A[N].  1 u v: Flip A[u,v]. After this operation, the N elements would be in the following order:
A[1], A[2], ... A[u1], A[v], A[v1], ... A[u+1], A[u], A[v+1], A[v+2], ... A[N].
For this problem, a string is an array of positive integers. Additionally, the number of different integers used in a string must be same as 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.
Since the result can be extremely large, you just have to print it modulo 1,000,000,007(10^{9} + 7)
Input
The first line of the input contains 2 space separated integers, N and M. N is the length of suffix array, and M is the number of operations.
Each of the next M lines contains 3 space separated integers representing an operation of one of the two types.
Output
Output a single line containing the number of strings corresponding to the given suffix array modulo 1,000,000,007(10^{9} + 7) .
Constraints
 1 ≤ N ≤ 1,000,000,000 (10^{9})
 0 ≤ M ≤ 100,000 (10^{5})
 For all operations, 1 ≤ u ≤ v ≤ N
Example
Input: 4 2 1 2 3 0 3 4 Output: 4
Explanation
The initial array is (1, 2, 3, 4).
After the first operation the array becomes (1, 3, 2, 4).
After the second operation the array becomes (2, 4, 1, 3).
The 4 possible strings are (2, 1, 2, 2), (2, 1, 3, 2), (3, 1, 3, 2), (3, 1, 4, 2).
Author:  tuananh93 
Tester:  keshav_57 
Editorial  http://discuss.codechef.com/problems/TASUFFIX 
Tags  binarytree, cook36, hard, splaytree, tuananh93 
Date Added:  15052013 
Time Limit:  5 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 