Problem Description

Utkarsh is on his way to Q shrines on the X axis. The ith Shrine is present at X=Li. For each shrine, Utkarsh will start at X=0 and move forward with the help of an array A of size N which will help him to reach the shrines. To move forward he must choose an index 1 which allows him to jump A[i] units forward in the positive X axis.

Utkarsh hates forgetting the past so he has an initially empty stack S to help him remember which indices of the array he chose. More specifically whenever he chooses index i of A, he pushes i at the top of the stack S.

Utkarsh will only be able to enter the ith shrine if he is at X=Li and |S|>0. However, the converse is not true, i.e., Utkarsh may choose to not enter the shrine even if the above conditions are satisfied.

Since Utkarsh is getting thinner nowadays, he would be able to carry stacks of size at most K.

Utkarsh wonders how many different stacks can he have when he enters the ith shrine.
(Two stacks are considered different iff they have different sizes or they contain different index value at some position)

Output the answer modulo 10^9+7 for each shrine.

Output 0 if he cannot enter the ith shrine.

INPUT

First line contains N and K.
Next line contains the array A.
Next line contains Q.
Next line contains all the Li.

OUTPUT

For each shrine, output the number of possible stacks modulo 10^9+7.

CONSTRAINT

• N
• 1
• 0
• Q
• 0

Example

INPUT
5 3
0 0 1 1 2
3
0 1 3

OUTPUT
14
34
36

Explanation
Valid stacks for first query are {1}, {2}, {1,2}, {2,1}, {1,1}, {2,2}, {2,1,1}, {1,2,1}, {1,1,2}, {2,2,1}, {2,1,2}, {1,2,2}, {1,1,1}, {2,2,2}