Sereja and Permutations 3

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Let p be a permutation of integers 1, ..., N. Lets call p good if there is at least one pair of indices (i,j) such that i < j and p[i] > j, p[j] > i. Sereja is interested in the number of permutations p of 1, ..., N that are good. This might seem easy at first, but Sereja is only interested in permutations that obey a list of M additional rules. Rule number i (1 ≤ i ≤ M) in Sereja's list says p(X_{i}) should equal V_{i}. Help Sereja count number of good permutations that obey the M additional constraints. As this number can be quite large, you should only output its value modulo 2000000011.Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. Each test case starts with line that contains two numbers N, M. The rest of the test cases consists of M lines describing Sereja's additional rules. The i'th such line gives the integers X_{i} and V_{i}.Output
Output one line per test case that gives the number of good permutations obeying Sereja's constraints modulo 2000000011.Constraints
 1 ≤ T ≤ 10
 1 ≤ N ≤ 10^9
 0 ≤ M ≤ 10^4
 1 ≤ X_{i}, V_{i} ≤ N
Example
Input: 2 3 0 3 2 3 1 1 2 Output: 1 0
Explanation
Example case 1. The only good permutation is 3,2,1 (i = 1, j = 2).
Sub tasks
 Subtask #1: 1 ≤ N ≤ 8 (5 points)
 Subtask #2: 1 ≤ N ≤ 20 (10 points)
 Subtask #3: 1 ≤ N ≤ 1000 (15 points)
 Subtask #4: 1 ≤ N ≤ 10000 (15 points)
 Subtask #5: 1 ≤ N ≤ 100000000 (20 points)
 Subtask #6: original (35 points)
Author:  sereja 
Tester:  xcwgf666 
Editorial  http://discuss.codechef.com/problems/SEAPERM3 
Tags  dynamicprogramming hard matrixexpo nov16 sereja 
Date Added:  7102016 
Time Limit:  3 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.4, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC 
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. 