Yet Another Query Problem!

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

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)

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.