# Sum Of Infinite Array

Last Updated: 11 Nov, 2020
Difficulty: Moderate

## PROBLEM STATEMENT

#### Note :

``````The value of the sum can be very large, return the answer as modulus 10^9+7.
``````
##### Input format :
``````The first line of input contains a single integer T, representing the number of test cases or queries to be run.

Then the T test cases follow.

The first line of each test case contains a single integer N, denoting the size of the array “A”.

The second line of each test case contains N single space-separated integers, elements of the array “A”.

The third line of each test case contains a single integer Q, denoting the number of queries.

Then each of the Q lines of each test case contains two single space-separated integers L, and R denoting the left and the  right index of the infinite array “B” whose sum is to be returned.
``````
##### Output format :
``````For each test case, print Q space-separated integers that denote the answers of the given Q queries.
Print the answer to each test case in a separate line.
``````

#### Note :

``````You do not need to print anything, it has already been taken care of. Just implement the given function.
``````
##### Constraints :
``````1 <= T <= 100
1 <= N <= 10^4
1 <= A[i] <= 10^9
1 <= Q <= 10^4
1 <= L <= R <= 10^18

Time Limit: 1sec
``````

## Approach 1

• Instead of creating a new infinite array B which has a repeated array A elements in the form [A1, A2,... AN, A1, A2,... AN, A1, A2,... AN…....]. We will traverse array A, again and again, to find the sum as array A is only repeating in infinite array B.
• So the brute force approach is, for each query,
• we run a loop from L to R, and for each index i, add the value at index (i%N) of the array A i.e A[i%N] to sum. So this way we can find the sum of the required subarray from index L to R in an infinite array B.