SOLVE
LATER
Given an array $$A$$ consisting of $$K$$ integers, today, you need to construct an awesome sequence $$S$$. An awesome sequence $$S$$ has the following properties:
It is infinite in length, and the $$0^{th}$$ element of the sequence is $$1$$.
After having the $$0^{th}$$ element of the sequence, in each following step, the entire sequence existing till now, is appended to the end of it. For example, if the sequence till now is $$(x, y)$$, it becomes $$(x, y, x, y) $$
Now, assume the indices of the elements appended to the sequence in the previous step ranges from $$L$$ to $$R$$. So, you need to modify all elements ranging from $$L$$ to $$R$$ in sequence $$S$$ as per the following formula :
$$\forall i$$ where $$L \le i \le R$$, : $$S_{i}$$ = $$ S_{i} + A[(i\space mod \space K)] $$ , where mod represents the remainder on division of $$i$$ by $$K$$
Follow steps $$2$$ and $$3$$ recursively until infinity.
Now, in addition to this, you shall be given $$Q$$ queries, In each query you shall be given a single integer $$M$$. You need to find and print for the $$i^{th}$$ query, the element present at index $$M_{i}$$ of the sequence. As the answer to each query can be rather large, print it Modulo $$10^9+7$$ .
Input Format :
The first line contains a single integer $$K$$. The next line contains $$K$$ space separated integers denoting the elements of array $$A$$. The next line contains a single integer $$Q$$. Each of the next $$Q$$ lines contains a single integer $$M$$, the parameter for the $$i^{th}$$ query.
Output Format :
For each query, print the answer on a single line.As the answer can be rather large, print it Modulo $$10^9+7$$.
Constraints :
$$ 1 \le K \le 10^5 $$
$$ 0 \le A[i] \le 10^9 $$
$$ 1 \le Q \le 10^5 $$
$$ 0 \le M \le 10^{15} $$
Firstly, the sequence consists of only element $$(1)$$. Then, we append the current sequence to its end, thus, it becomes $$(1,1)$$.
In this last step, elements from index $$1$$ to $$1$$ were added to the end of the sequence. Thus we need to modify all these elements. As a result of this, the element at index $$1$$ becomes $$3$$. So, the sequence becomes $$(1,3)$$.
Then again, we append the current sequence to its and, and the new sequence is $$ (1,3,1,3)$$. Then again, we modify elements from index $$2$$ to $$3$$ and so on. As a result of this, the sequence becomes $$ (1,3,4,7)$$.
This procedure is carried on until infinity.