Problem Description
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