# Sum Of Infinite Array

Posted: 11 Nov, 2020

Difficulty: Moderate

#### Given an array “A” of N integers and you have also defined the new array “B” as a concatenation of array “A” for an infinite number of times.

#### For example, if the given array “A” is [1,2,3] then, infinite array “B” is [1,2,3,1,2,3,1,2,3,.......].

#### Now you are given Q queries, each query consists of two integers “L��� and “R”(1-based indexing). Your task is to find the sum of the subarray from index “L” to “R” (both inclusive) in the infinite array “B” for each query.

#### 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
```