### 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 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))