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