GP Subsequences :
Difficulty Level : Hard
Submissions : 868
Asked In :
Marks :20
: 7 | : 1
You are given an array $$$A$$$ containing $$$n$$$ integers. Your task is to determine the number of subsequences of length $$$\ge 2$$$ such that they form a Geometric Progression with a prime common ratio.
A subsequence is a sequence that can be derived from the given sequence by deleting zero or more elements without changing the order of the remaining elements. Two subsequences are considered different if they contain different indices of elements.
The first line of input contains an integer $$$n$$$ $$$(1 \le n \le 10^4)$$$ — the number of elements in the array $$$A$$$.
The second line of input contains $$$n$$$ space separated integers $$$A_1, A_2, ... A_n$$$ $$$(1 \le A_i \le 10^5)$$$ — the elements of array $$$A$$$ respectively.
Print a single integer — the number of subsequences of length $$$\ge 2$$$ such that they form a geometric progression with a prime common ratio. Since the number of subsequences can be rather large, print the answer modulo $$$10^9 + 7$$$.
3 1 2 4
3
5 2 3 4 6 18
5
In sample test case 1, the GP subsequences are $$${[1,2], [2,4], [1,2,4]}$$$.
In sample test case 2, the GP subsequences are $$${[2,4], [2,6], [3,6], [6,18], [2,6,18]}$$$.
