Awesome Sequence
Tag(s):

## Binary Search, Dynamic Programming, Easy-Medium, Math, Recursion

Problem
Editorial
Analytics

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:

1. It is infinite in length, and the $0^{th}$ element of the sequence is 1.

2. 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)$

3. 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

4. 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}$

SAMPLE INPUT
5
1 2 3 4 5
5
0
1
5
10
20
SAMPLE OUTPUT
1
3
4
5
7
Explanation

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.

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

Lenskart Java Hiring Challenge

OTHER PROBLEMS OF THIS CHALLENGE
• Data Structures > Advanced Data Structures