DCEPC14D - Finding GP

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<=10000
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

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

hide comments
2018-05-17 04:50:41
I donot get the problem!
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
2015-07-08 10:33:50 રચિત (Rachit)
You need to find GPs counting duplicates. It should be more clarified in the problem statement IMHO.
2015-05-30 21:58:45 vivek
More Test Cases Please!
2015-05-03 16:13:19 Akshay Jain
Can you please explain how you got 41 for the case mentioned so that it becomes clear which cases to take and which not.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.