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 simply gets tempted 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 ≤ 107).

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 ≤ 103) denoting the number of test cases. Each of the following lines will contain two numbers N and Z (- 1 ≤ Z ≤ N ≤ M ≤ 107).

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.