A14709 | Max Sum Array

You are given an array $c = [c_1, c_2, \dots, c_m]$ . An array $a = [a_1, a_2, \dots, a_n]$ is constructed in such a way that it consists of integers $1, 2, \dots, m$ , and for each $i \in [1,m]$ , there are exactly $c_i$ occurrences of integer $i$ in $a$ . So, the number of elements in $a$ is exactly $\sum\limits_{i=1}^{m} c_i$ .

Let's define for such array $a$ the value $f(a)$ as $$$$f(a) = \sum_{\substack{1 \le i < j \le n\\ a_i = a_j}}{j - i}. $$ </p><p>In other words, $f(a)$ is the total sum of distances between all pairs of equal elements.</p><p>Your task is to calculate the maximum possible value of $f(a)$ and the number of arrays yielding the maximum possible value of $f(a)$$$. Two arrays are considered different, if elements at some position differ.

The first line contains a single integer $m$ ( $1 \le m \le 5 \cdot 10^5$ ) — the size of the array $c$ .

The second line contains $m$ integers $c_1, c_2, \dots, c_m$ ( $1 \le c_i \le 10^6$ ) — the array $c$ .

Print two integers — the maximum possible value of $f(a)$ and the number of arrays $a$ with such value. Since both answers may be too large, print them modulo $10^9 + 7$ .