Last Updated: 30 Dec, 2020

# Number of GP sequence

Moderate

## Problem statement

#### A geometric progression (GP), also called a geometric sequence, is a sequence of numbers that differ from each other by a common ratio. For example, the sequence 2,4,8,16,… is a geometric sequence with common ratio 2.

##### Note:
``````As the answer can be very large you need to return the answer in mod 10^9+7.
``````
##### Input Format:
``````The first line of the input contains an integer ‘T’ denoting the number of test cases.

The first line of each test case contains two space-separated positive integers ‘N’ and ‘R’ denoting the number of the elements present in the array and the common ratio of GP.

The second line of each test case contains ‘N’ space-separated integers denoting the elements of the array.
``````
##### Output Format:
``````The only line of output of each test case should contain the number of the subsequence of length 3 having a common ratio ‘R’.
``````
##### Note:
``````You do not need to print anything, it has already been taken care of. Just implement the given function.
``````
##### Constraints:
``````1 <= T <= 50
3 <= N <= 10^4
1 <= R <= 10^4
1 <= A[i] <= 10^9

Time Limit: 1 sec
``````

## Approaches

### 01 Approach

• We want subsequences of length 3 so we can use 3 nested loops to check all possible subsequences that are in GP or not.
• If the first number is A[i] then the next two numbers should be A[i]*R and A[i]*R^2 respectively. If they are matching then we increment our answer by one.
• Take mod at each step and finally return the answer.