Sankalp's obsession for GCD is increasing day by day. Now he came up with this GCD question.

The goodness of array is defined as the product of sum of all the elements of the array and GCD of all the elements of the array.

In other words goodness of array temp of size k is equal to (temp[1] + temp[2] + ... + temp[k]) * gcd(temp[1], temp[2] ... temp[k]).

In this task you will be given an array and you have to find the sum of goodness of all non-empty subsequences of the given array.

Since the answer can be very large output it modulo 1 000 000 007 (1e9+7).

Definition of: Subsequence

Input

First line of the input is the number of elements in the given array.

Next line contains space separated array elements.

Output

Output the sum of goodness all the non-empty subsequences of the given array modulo 1e9+7.

Constraints

1 ≤ n ≤ 1 000 000

1 ≤ arr[i] ≤ 1 000 000

Example

Input:
2 4 6 9
Output:
350

Explanation

There will be 15 non-empty subsequences of the given array given as [2], [4], [6], [9], [2, 4], [2, 6], [2, 9], ... too lazy to write them all :P

Required ans = 2*2 + 4*4 + 6*6 + 9*9 + 6*2 + 8*2 + 11*1 + ... = 350.

Let me know in the comments if it doesn't match :P