## Problem Description

Given m positive integer a[1],a[2]…a[m]. We run the following program (in C++):

const int MAXN = 20;
int a[MAXN], m;
int gcd(int a, int b) {return b ? gcd(b, a % b) : a;}
long long cnt = 0;
void gao(int cur, int g) {
if (cur > m) {
if (g == 1)++cnt;
return;
}
for (int i = 1; i <= a[cur]; ++i)
gao(cur + 1, g < 0 ? i : gcd(g, i));
}
int main() {
scanf("%d", &m);
for (int i = 1; i <= m; ++i)
scanf("%d", a + i);
gao(1, -1);
cout << cnt << endl;
return 0;
}

Here gcd is the Greatest Common Divisor, Obviously, the program above is to find the number of tuples (b[1], b[2], …, b[m]) such that:

(1) gcd(b[1], b[2], …, b[m])=1. (Here we define gcd(num)=num, that is: gcd(9)=9, gcd(2)=2)

(2) 1≤b[i]≤a[i]. (1≤i≤m, b[i] is an integer)

Now in this problem, the m and a[i] may be very large! So could you write one efficient program to find the answer? The answer may be too large. So you can just output the answer Mod 1,000,000,007.

## Input

The first line of the input contains an integer T (T≤10,000), indicating the number of test cases.

Then T cases, for any case, only two lines.

The first line is one integer m(1≤m≤20).

The second line has m integers indicate a[1], a[2], …, a[m] (1≤a[i]≤100,000,000, 1≤i≤m).

The answer may be too large. So you can just output the answer Mod 1,000,000,007.

## Output

For each test case, print a line containing the answer Mod 1,000,000,007.

## Sample Input

3
2
5 5
2
10000 9873
2
1234 5678

## Sample Output

19
60026156
4261566

## Hint

In the first case, we have 5*5=25 tuples: (1, 1), (1, 2), …, (5, 3), (5, 4), (5, 5). Only 19 of them have the gcd 1. This problem is not very easy, and you have to make sure that you find one efficient algorithm.

## Source

“高教社杯”第三届福建省大学生程序设计竞赛