P8469 [Aya Round 1 D] Wende’s Math Game

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

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$.

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

- 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$.

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