Maximum GCD and Counting Sequences

Given an integer sequence \(a = (a_1, a_2, \ldots, a_n)\), construct another sequence \(b = (b_1, b_2, \ldots, b_n)\) such that for every \(1 \le i \le n\), \(1 \le b_i \le a_i\). You are to choose \(b\) in order to maximize the value of \(\gcd(b_1, b_2, \ldots, b_n)\) and to count the number of sequences \(b\) achieving this maximum value, modulo \(10^9+7\).

If the optimal value of \(\gcd(b_1,b_2,\ldots,b_n)\) is \(X\), then there exists integers \(k_1,k_2,\ldots,k_n\) such that \(b_i = X \times k_i\) and \(1 \le X\times k_i \le a_i\). Equivalently, \(1 \le k_i \le \left\lfloor\frac{a_i}{X}\right\rfloor\). In order for \(\gcd(b_1,b_2,\ldots,b_n)=X\), we require \(\gcd(k_1,k_2,\ldots,k_n)=1\).

Notice that choosing \(X = \min(a_1,a_2,\ldots,a_n)\) always provides a valid solution because for the index \(j\) with \(a_j=\min(a)\) we have \(\left\lfloor\frac{a_j}{X}\right\rfloor=1\) forcing \(k_j=1\) and thus \(\gcd(k_1,k_2,\ldots,k_n)=1\). Therefore, the maximum attainable \(\gcd(b_1,b_2,\ldots,b_n)\) is \(\min(a_1,a_2,\ldots,a_n)\).

The number of ways to achieve this maximum is given by:

[ \text{ways} = \prod_{i=1}^{n} \left\lfloor\frac{a_i}{\min(a)}\right\rfloor \mod (10^9+7). ]

Two sequences are considered different if there exists at least one index \(i\) such that the elements at that index differ.

inputFormat

The first line contains an integer \(n\) (\(1 \le n \le 10^5\)), the length of the sequence \(a\).
The second line contains \(n\) integers \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le 10^9\)).

outputFormat

Output two space-separated integers: the maximum value of \(\gcd(b_1,b_2,\ldots,b_n)\) and the number of sequences achieving it modulo \(10^9+7\).

sample

3
3 6 8

3 4