Background

After solving the previous problem, Cirno felt as if she were a genius. So, Shameimaru Aya gave her another simple math problem.

Problem Description

Given an integer sequence $a$ of length $n$, you need to construct an integer sequence $b$ of length $n$ such that for all $1 \le i \le n$, we have $1 \le b_i \le a_i$. Also, $\gcd(b_1,b_2,\cdots,b_n)$ should be as large as possible, where $\gcd$ denotes the greatest common divisor. Find the maximum possible value and, when this maximum is achieved, the number of different sequences $b$, modulo $10^9+7$.

Two sequences $c, d$ of length $L$ are considered different if and only if there exists an integer $i(1 \le i \le L)$ such that $c_i \ne d_i$.

Input Format

• The first line contains an integer $n$.
• The second line contains $n$ integers, representing the sequence $a$.

Output Format

• Output one line with two integers: the maximum $\gcd(b_1,b_2,\cdots,b_n)$ that can be obtained, and the number of corresponding different sequences $b$ achieving this maximum, modulo $10^9+7$.

3
1 2 3

1 6

Hint

Sample 1 Explanation

Note that since $1 \le b_1 \le a_1 = 1$, $b_1$ must be $1$. Therefore, the maximum possible $\gcd$ value can only be $1$. Under this condition, all valid $b$ are as follows:

• $\{1,1,1\},\{1,1,2\},\{1,1,3\},\{1,2,1\},\{1,2,2\},\{1,2,3\}$.

Constraints

For $100\%$ of the testdata, $1 \le n \le 10^5$, $1 \le a_i \le 10^9$.

This problem comes with a set of large samples.

Translated by ChatGPT 5