Jhakaas has been given a list X of length L, Apptica being creative devises an operation defined as

Operate(X):
    for i = 1 to L-1 
        X[i] += X[i+1]

Apptica challenges Jhakaas to answer his Q queries. In each query, Apptica will run this operation Z times on the initial list and will ask Jhakaas to answer the value of the ith element (1 based indexing) of the list modulo 10⁹ + 7. Jhakass is feeling too sleepy to play the game, he needs your help to win.

INPUT:

The first line of each test file contains an integer L denoting the size of the list.

The second line will contain integers X_i i.e the elements of the array X.

The third line will contain another integer Q and the next Q lines will contain i and Z, list index and the number of times the operation was performed on the initial list.

OUTPUT:

For each query, you will have to print the value of the ith index (modulo 10⁹ + 7) in a new line .

CONSTRAINTS:

1 <= N * Q <=10⁶

1 <= X_i <=10¹⁸

1 <= Z <= 10¹⁸