G. Divine Powers
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Given an array $$$a$$$ of length $$$n$$$, you need to calculate the following sum:

$$$$$$ f(a)=\frac{\large \prod_{i=1}^{n} \frac{a_i}{\phi(a_i)}}{gcd(a_1,...,a_n)} \bmod 10^9+7 $$$$$$

Since the authors thought the above problem was too easy, you need to calculate the summation of $$$f(s)$$$ across all non-empty subsequences $$$s$$$ in the array $$$a$$$. Formally, you need to calculate:

$$$$$$ \large \sum_{\emptyset \neq s \subseteq a} f(s) \bmod 10^9+7 $$$$$$

Here $$$\phi(k)$$$ denotes the euler totient function. Note that a subsequence of a given array is a sequence that can be derived from the given array by deleting some or no elements without changing the order of the remaining elements.

Input

The first line contains a single integer $$$n$$$ ($$$1\le n\le 10^6$$$) — the size of the array $$$a$$$.

The second line contains $$$n$$$ integers $$$a_1$$$,$$$a_2$$$,…,$$$a_n$$$ ($$$1\le a_i\le 10^6$$$) — the elements of array $$$a$$$.

Output

Print a single integer — The summation of $$$f(s)$$$ across all non-empty subsequences $$$s$$$ in the array $$$a$$$ modulo $$$1000000007$$$.

Example
Input
4
1 2 3 4
Output
500000042