DCEPC14D - Finding GP

no tags 

There is an array A of n elements . You need to tell the number of subsets of size greater than 1 which can form geometric progressions having integral common ratios.

Constraints:

1<=N<=1*10^4
1<=A[i]<=1000000

Input

The first line contains a single integer denoting the number of integers in the array (N). The second line contains N space separated integers representing the elements of the array.

Output

The output should contain a single line with the answer to this problem MODULUS 1000000007 . 

Example

Input:
7
2 4 4 2 8 16 8

Output:
41

hide comments
nimphy: 2018-05-17 04:50:41

I donot get the problem!

kmkhan_014: 2017-12-21 20:00:13

Great feeling AC in one go!!!the problem statement is unclear.
some test cases to clear any confusion:
3
4 2 1 o/p = 4

Last edit: 2017-12-21 20:06:45
રચિત (Rachit): 2015-07-08 10:33:50

You need to find GPs counting duplicates. It should be more clarified in the problem statement IMHO.

vivek: 2015-05-30 21:58:45

More Test Cases Please!

Akshay Jain: 2015-05-03 16:13:19

Can you please explain how you got 41 for the case mentioned so that it becomes clear which cases to take and which not.


Added by:dce coders
Date:2015-04-26
Time limit:0.600s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 JS-MONKEY