# Practice on Toph

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

# Purity Test

Nowadays nothing is pure. Be it a heart or a food or just a mere number. There is contamination in almost everything. Whatever you see is not real or pure anymore. But it’s time to make the world pure again. In order to do so, we first need to check whether something is pure or not.

You don’t trust anyone. So, you have made a function that can calculate purity level:

```
function Purity(N, Z)
Count = 0
Sum = 0
For i_1 = 1 to N
For i_2 = 1 to N
For i_3 = 1 to N
...
For i_Z = 1 to N
if Valid[ GCD(i_1, i_2, i_3, ... , i_Z) ] equals 1
Count = Count + 1
Sum = Sum + GCD(i_1, i_2, i_3, ... , i_Z)
end if
end For
...
end For
end For
end For
return {Count, Sum}
end function
```

But to you, this function looks way too complicated to use. Nihaz is your best friend and an awesome problem solver (way more awesome than you are). But the weird thing is that, whenever you look at him you notice that, he **s**imply **g**ets **t**empted to **laugh** at you. And you start wondering “Do I look like a joker ? 😐”. Using your function Nihaz has figured out the purity of everything. Now you will reveal the true purity of everything in front of the whole world.

Let, `$ GCD(i_1, i_2, i_3, ..., i_Z) $`

is the greatest common divisor of `$ i_1 $`

, `$ i_2 $`

, `$ i_3 $`

, … and `$ i_Z $`

. `$ GCD(x) = x $`

.

## Input

The first line contains an integer **M** (- 1 ≤ Z ≤ N ≤ M ≤ 10^{7}).

Following line will have M integers containing the values of the array **Valid[]** (0 ≤ Valid[i] ≤ 1).

The next line there will be an integer **T** ( 1 ≤ T ≤ 10^{3}) denoting the number of test cases. Each of the following lines will contain two numbers **N** and **Z** (- 1 ≤ Z ≤ N ≤ M ≤ 10^{7}).

## Output

For each test case, output the answers of the purity function in a single line.

As the results can be very big, print the remainders of the results when divided with 1000000007.

## Samples

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

5 1 1 0 0 1 3 2 2 4 2 5 2 | 4 5 14 17 23 30 |

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

10 1 1 1 0 1 0 1 0 0 0 10 1 2 2 2 3 2 4 2 5 2 6 2 7 2 8 2 9 2 10 2 | 1 1 4 5 9 12 15 20 24 33 34 51 47 70 59 86 75 110 93 144 |

The data set is huge. Please use fast I/O methods.

#### IamHot

→