Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Yet Another Query Problem!

By emrul_mu · Limits 2s, 512 MB

You are given an array $A$ of length $n$ consisting of integers between $1$ and $10^6$. You need to perform $m$ queries on the array.

In each query, there will four integers $l, r, x$ and $k$. You need to answer that how many subsequences of length $k$ exists in subarray $[l, r]$ (where $l$ is the starting position of the subarray and $r$ is the ending position) of the array $A$ where every element of the subsequence is divisible by $x$.

Answers can be very large, so you need to print the answer modulo $10^9 + 7$.

Input

The first line contains a two integer, $n$ and $m$, denoting the length of array $A = [a_1, a_2,..., a_n]$ and the number of queries respectively.

The second line contains $n$ space-separated integers describing each respective element, $a_i$, in array $A$.

Each of the next $m$ lines contains four integers $l, r, x$ and $k$, denoting a query.

Constrains

$1\leq n\leq10^6$
$1\leq m\leq2*10^5$
$1\leq a_i, x\leq10^6$
$1\leq l\leq r\leq n$
$1\leq k\leq r-l+1$

Output

For each query, print the required answer in separate lines.

Sample

InputOutput
10 3
1 2 3 4 5 6 7 8 9 10
2 8 4 1
2 8 4 2
1 10 2 2
2
1
10

For third query, there are total 5 numbers in the range [1, 10] which is divisible by 2 (2, 4, 6, 8, 10). And all subsequence of length 2 are (2, 4), (2, 6), (2, 8), (2, 10), (4, 6), (4, 8), (4, 10), (6, 8), (6, 10), (8, 10)


Note

A subarray of an $n$ element array is an array composed of a contiguous block of the original array’s elements. For example, if $array = [1, 2, 3]$, then the subarrays are $[1]$, $[2]$, $[3]$, $[1, 2]$, $[2, 3]$, and $[1, 2, 3]$. Something like $[1, 3]$ would not be a subarray as it’s not a contiguous subsection of the original array.

    Discussion

    Statistics


    50% Solution Ratio

    EgorKulikovEarliest, 1w ago

    pathanFastest, 0.9s

    EgorKulikovLightest, 84 MB

    aritra741Shortest, 1685B

    Submit

    Login to submit