5153：A card problem

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)$.

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)$.

For each test case, output the remainder of division of the resulting number by $1000000007({10}^{9}+7)$.