Mock Turtle

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
The Mock Turtle went to the ocean's school to become a true turtle! However instead of practicing the usual operations of addition, subtraction and division taught by the lecturers, she was always playing with parentheses.
A parentheses is defined using the following rules:
 An empty string is a parentheses.
 If X is a parentheses, then (X) is also a parentheses
 If X and Y are parentheses, then XY is also a parentheses
 Every parentheses can be created using the previous rules only.
A parentheses contains k blocks if it can be represented as the concatenation of exactly k non empty parentheses, but can not be represented as the concatenation of more than k non empty parentheses. For example ()(()) contains two blocks (i.e. () and (())) and (()()) contains just one block.
Every time Alice meets with the Mock Turtle they create two arrays of integers a and b both of length N, and play the following game T times: First Alice thinks of two integers L and R, then the Mock Turtle chooses two integers i, j such that L ≤ i, j ≤ R and builds all the parentheses of length a_{i} that contains b_{j} blocks. Since the Mock Turtle loves building parentheses, she will choose i, j in such a way that number of parentheses of length a_{i} that contains b_{j} blocks are maximized.
Input
The first line of the input contains two integers N, T .
The following two lines containing N space separated integers representing the elements of array a and b respectively.
Then follows T lines, each one have two integers L and R representing one game.
Output
For each game, output a single line containing the answer to the problem, since this number can be very large print it modulo 10^{9}+7.
Constraints
 1 ≤ N, T ≤ 10^{5}
 1 ≤ a_{i}, b_{i} ≤ 2·10^{5}, a_{i} is even
 1 ≤ L ≤ R ≤ N
Example
Input: 5 2 4 6 2 4 8 3 3 3 3 3 2 4 1 5 Output: 1 3
Explanation
In the first query the Mock Turtle can build only the parentheses ()()()
In the second query the three possible parentheses are
 ()()(())
 ()(())()
 (())()()
Author:  alei 
Tester:  kingofnumbers 
Editorial  http://discuss.codechef.com/problems/MCKTUR 
Tags  alei, catalan, combinatorics, cook73, medium 
Date Added:  21072016 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, 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, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions