Sereja and Inversions

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Sereja has a permutation P of the N numbers in the range 1 to N. You have to answer M queries over it, where each query is given four numbers l_{1}, r_{1}, l_{2}, r_{2} (1 ≤ l_{1} ≤ r_{1} < l_{2} ≤ r_{2} ≤ N, r_{1}  l_{1} = r_{2}  l_{2}). Your task is to calculate number of permutations Q of the S integers in the range 1 to S, such that S = r_{1}  l_{1} + 1, and for each i from 1 to S, the condition P_{Qi + l1  1} < P_{i + l2  1} is satisfied.
Please help Sereja in providing the answer for each query modulo 10^{9} + 7.
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
First line of each test case contains two space separated integers N, M.
Next line contains numbers P_{1}, P_{2}, ..., P_{N}.
Each of next M lines contains numbers l_{1}, r_{1}, l_{2}, r_{2}  denoting the query.
Output
For each query, output the corresponding answer in single line.
Constraints
 1 ≤ T ≤ 10
 1 ≤ sum of all N over all test cases ≤ 10^{5}
 1 ≤ sum of all M over all test cases ≤ 10^{5}
Subtasks
 Subtask #1: (10 points) 1 ≤ N ≤ 10
 Subtask #2: (20 points) 1 ≤ N ≤ 1000
 Subtask #3: (70 points) original constraints plus additionally 0 ≤ number of pairs i, j (1 ≤ i < j ≤ N, P_{i} > P_{j}) over all test cases ≤ 3*10^{6}
Example
Input: 3 4 1 1 2 3 4 1 2 3 4 4 2 1 3 2 4 1 1 2 2 1 2 3 4 10 1 1 4 3 2 9 5 6 7 10 8 1 5 6 10 Output: 2 1 1 24
Author:  sereja 
Tester:  mgch 
Tags  sereja 
Date Added:  16102016 
Time Limit:  2 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