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