Given m positive integer a[1],a[2]…a[m]. We run the following program (in C++):
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.
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.
3 2 5 5 2 10000 9873 2 1234 5678
19 60026156 4261566