Weird Queries

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
You are given a list of M positive numbers, A_{0}, A_{1}, ..., A_{M1}. You have to answer Q queries. Each query has four parameters, l, r, n, k. Given a query with parameters l, r, n, k here is how to compute the answer:
 Let (B_{1}, B_{2} ..., B_{d}) = (A_{l}, A_{l+1}, ... ,A_{r}), where d = rl+1.
 Let S = set of all points (x_{1}, x_{2}, ..., x_{d}) in ddimensional space such that 0 < x_{i} ≤ B_{i}.
 For x, y ∈ S, define dist(x, y) = min_{1 ≤ i ≤ d}  x_{i}  y_{i} 
 The answer is number of subsets of S of size exactly n such that distance (denoted by above defined dist function) between any two points is at least k.
Input
The first line of input contains two integers, M and Q. The second line contains M spaceseparated integers A_{0}, A_{1}, ..., A_{M1} denoting the array A. The next Q lines contain one query each. Each query consists of a single line having the four space separated integers l, r, n, k in this order.
Output
For each query, output a single line containing the answer modulo 1000000007 (10^{9} + 7).
Constraints
 1 ≤ M ≤ 5 × 10^{5}
 1 ≤ Q ≤ 3 × 10^{5}
 1 ≤ A_{i} ≤ 10^{5}
 ∑ _{0 ≤ i < M} A_{i} ≤ 3 × 10^{6}
 For each query, 0 ≤ l ≤ r < M
 1 ≤ k ≤ 10^{5}
 0 ≤ n ≤ 10^{5}
Example
Input: 5 2 4 5 4 6 2 0 3 1 1 2 2 2 3 Output: 480 1
Explanation
For the first query, the answer is 4 * 5 * 4 * 6, because we just have to choose one coordinate from each dimension.
For the second query, the array B = [4] and you have to pick two positive integers less than or equal to 4 such that the distance between them is 3 or more. There is only way to do this: pick 1 and 4.
Author:  utkarsh_lath 
Tags  utkarsh_lath 
Date Added:  8072016 
Time Limit:  4 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. 