提示: 欢迎访问OurACM平台。
Problem 2106 How many tuples

Accept: 41    Submit: 215
Time Limit: 10000 mSec    Memory Limit : 65536 KB

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

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

Submit  Back  Status  Discuss