JayYe is solving a card problem. His IQ is low recently, so he ask you for help.
In a room, there are $N$ tables numbered $1,2,3,бн,N$. There is a blue card on each table. The ith card is on the ith table. On the ith blue card, there is a number $A_{i}$. Now you can put on a red card on each table and the number on the ith red card is $B_{i}(1\leq B_{i}\leq A_{i})$. Then a problem comes, for one arrangement how many pair of $(i,j)$ that satisfy $i < j$ and $ gcd(B_{i},B_{j})$ has at most one different prime factor? We call these pairs $good pairs$. For example, 12 has two different prime factors. $(12=2*2*3)$
But this is not you problem. You can easily know there are $\prod\limits_{i=1}^{N}A_{i}$ different arrangements. Your task is to calculate the sum of the number of $good pairs$ of all different arrangements. As the answer can be rather large, find remainder after dividing the number by $1000000007({10}^{9}+7)$.
Input
There are several test cases.
In each test case:
The first line contains a integer $N(1\leq N\leq 100000)$. The second line contains $N$ integers $A_{1},A_{2},A_{3},...A_{N}(1\leq A_{i}\leq 100000,1\leq i\leq N)$.
Output
For each test case, output the remainder of division of the resulting number by $1000000007({10}^{9}+7)$.
Sample Input
2
2 5
2
10 10
Sample Output
10
98
Hint
In the first test case, there are 10 different arrangements:
{1,1} {1,2} {1,3} {1,4} {1,5} {2,1} {2,2} {2,3} {2,4} {2,5}.
All pairs are good, so answer is 10.
