### PROBLEM LINK

### Panel Members

**Problem Setter:** Suhash

**Problem Tester:**

**Editorialist:** Sunny Aggarwal

**Contest Admin:**

**Russian Translator:**

**Mandarin Translator:**

**Vietnamese Translator:**

**Language Verifier:**

### DIFFICULTY:

Medium

### PREREQUISITES:

Fermat little theorem, Number Theory, Subset Theory, Mathematics.

### PROBLEM:

Given an array A consisting of N integers where, each value A_i \le 10^5. We are asked to calculate the product of **gcd** of all non empty subset of array A modulo 10^9 + 7.

### EXPLANATION

Let us solve the following simpler problem first in order to understand the solution of original problem better.

**Problem Statement**

Given an array A consisting of N integers where, each value A_i \le 10^5. For each number i where i \in (1, 10^5), calculate the number of non empty subsets with **gcd = i** modulo 10^9 + 7.

Lets create an array S[] where S_i will contain the number of non empty subsets with **gcd = i** and an array F[] where F_i will contain the number of elements among given N elements that are multiple of i.

**How to construct array F ?**

It is given that each value in the array A i.e A_i \le 10^5. Therefore, we can simply pre compute the divisors for a given i where i \in [1, 10^5] and use following algorithm to fill array F.

**C ++ Code**

```
vector<int> div[ 100000 ];
void pre() {
for(int i=1; i<=100000; i++) {
int j = i;
while( j <= 100000 ) {
div[j].push_back( i );
j += i;
}
}
}
int F[100000];
void solve() {
int n;
cin >> n;
for(int i=1; i<=n; i++) {
int x;
cin >> x;
for( auto it: P[x] ) {
F[it] ++;
}
}
}
```

F_x stores the count of numbers which are multiple of x. Therefore, choosing any non empty subset of these numbers will produce **gcd** of any of these kind x, 2*x, 3*x â€¦ and so on ( multiples of x ) and if we know how many subsets are there which produces **gcd** = 2*x, 3*x, 4*x â€¦ and so on in advance, we can evaluate the number of subsets with **gcd = x** easily.

Above explanation is easy to understand with the following code.

```
void solve() {
for(int i=100000; i>=1; i--) {
int remove = 0;
int j = 2 * i;
while( j <= 100000 ) {
remove += S[j];
remove %= mod;
j += i;
}
int total = (power(2, F[i]) - 1); // number of non empty subsets
S[i] = total - remove; // removing subsets with gcd 2 * i, 3 * i...
if( S[i] < 0 ) {
S[i] += mod;
}
}
}
```

**Hurray !!** We have solved the simpler version of our original problem.

At this point, we know for each value x \in [1, 10^5], the number of subsets with **gcd = x** in S_x and our original problem asked for the following expression

Note that if a given x canâ€™t be gcd of any subset, then S_x = 0 and therefore it is correct to write above expression.

**How to compute above expression ?**

We cannot compute this expression easily as value of S_x can be very large. So, we will be using Fermat Little Theorem here. Fermatâ€™s Little theorem states that a^{p-1} = 1 mod p. Where p is prime. This is valid for all integers a. So if we want to calculate a^b mod ( p ) and b = k * (p-1) + m. Then we know a^b = (a^{p-1})^k * a^m = 1^k * a^m = a^m and therefore, we will be maintaining array S[] modulo (10^9 + 6) instead.

Please have a look at editorialistâ€™s solution for implementation details.

### COMPLEXITY

O(T*max(A_i) * \log(A_i))