问题描述
杰叶正在做一道卡片的题目。因为最近他的智商捉急，所以他现在需要你的帮助。
在一个房间里，摆放着$N$张桌子，标号分别为$1,2,3,…,N$。每张桌子上都有一张蓝色的卡片，第i张卡片在第i张桌子上。在第i张卡片上有一个数字，数字为$A_{i}$。现在你可以在每一张桌子上再放上一个红色的卡片，在第i张卡片上的数字为$B_{i}(1\leq B_{i}\leq A_{i})$。那么问题来了，由于每张卡片上的数字有很多种，对于一种放卡片的方案，有多少个pair对$(i,j)$满足$i < j$并且$gcd(B_{i},B_{j})$由不多于一个的质因子组成？我们把这些pair称为good pairs。比如说，12由两个不同的质因子组成，因为$12=2*2*3$。
但是这不是你要解决的问题。首先很容易能够知道总共有$\prod\limits_{i=1}^{N}A_{i}$种不同的放卡片的方案，你的任务是计算所有不同的放卡片的方案的$good pairs$的数量的和。由于答案可能很大，输出答案对$1000000007({10}^{9}+7)$取模。
输入说明
输入有多组测试数据。
对于每组测试数据：
第一行为一个整数$N(1\leq N\leq 100000)$
第二行为$N$个整数$A_{1},A_{2},A_{3},...A_{N}(1\leq A_{i}\leq 100000,1\leq i\leq N)$
输出说明
对于每组测试数据，输出答案对$1000000007({10}^{9}+7)$取模。
输入样例
2
2 5
2
10 10
输出样例
10
98
提示
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.
