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, A0, A1, ..., AM-1. 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 (B1, B2 ..., Bd) = (Al, Al+1, ... ,Ar), where d = r-l+1.
- Let S = set of all points (x1, x2, ..., xd) in d-dimensional space such that 0 < xi ≤ Bi.
- For x, y ∈ S, define dist(x, y) = min1 ≤ i ≤ d | xi - yi |
- 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.
The first line of input contains two integers, M and Q. The second line contains M space-separated integers A0, A1, ..., AM-1 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.
For each query, output a single line containing the answer modulo 1000000007 (109 + 7).
- 1 ≤ M ≤ 5 × 105
- 1 ≤ Q ≤ 3 × 105
- 1 ≤ Ai ≤ 105
- ∑ 0 ≤ i < M Ai ≤ 3 × 106
- For each query, 0 ≤ l ≤ r < M
- 1 ≤ k ≤ 105
- 0 ≤ n ≤ 105
Input: 5 2 4 5 4 6 2 0 3 1 1 2 2 2 3 Output: 480 1
ExplanationFor 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 =  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.
|Time Limit:||4 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, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.