All Tracks Basic Programming Recursion Recursion and Backtracking Problem

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++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala 2.11.8, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

Lenskart

Challenge Name

Lenskart Java Hiring Challenge

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications