# Practice on Toph

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

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

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$`

.

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.

`$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$`

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

Input | Output |
---|---|

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) |

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.

50% Solution Ratio

EgorKulikovEarliest,

pathanFastest, 0.9s

EgorKulikovLightest, 84 MB

aritra741Shortest, 1685B

Login to submit