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++, 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...
Your Rating:

Contributor

This Problem was Asked in

Lenskart

Challenge Name

Lenskart Java Hiring Challenge

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?