CF1612G.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 \lt j \le n\\ a_i = a_j}}{j - i}.$$

In other words, $f(a)$ is the total sum of distances between all pairs of equal elements.

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.

给你一个数组 $c = [c_1, c_2, \dots, c_m]$。按如下方式构造数组 $a = [a_1, a_2, \dots, a_n]$：它由整数 $1, 2, \dots, m$ 组成，且对每个 $i \in [1,m]$，整数 $i$ 在 $a$ 中恰好出现 $c_i$ 次。因此，$a$ 的元素个数恰好为 $\sum\limits_{i=1}^{m} c_i$。

我们定义该数组 $a$ 的值 $f(a)$ 为

$$f(a) = \sum\_{\substack{1 \le i < j \le n\\ a\_i = a\_j}}{j - i}.$$

换言之，$f(a)$ 是所有相等元素对之间距离的总和。

你的任务是计算 $f(a)$ 可能取得的最大值，以及能达到该最大值的数组 $a$ 的个数。若两个数组在某个位置上的元素不同，则认为它们是不同的数组。

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

第一行包含一个整数 $m$（$1 \le m \le 5 \cdot 10^5$）—— 数组 $c$ 的长度。

第二行包含 $m$ 个整数 $c_1, c_2, \dots, c_m$（$1 \le c_i \le 10^6$）—— 数组 $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$.

输出两个整数——$f(a)$ 的最大可能值，以及达到该最大值的数组 $a$ 的个数。由于这两个答案可能过大，请对 $10^9 + 7$ 取模后输出。

In the first example, all possible arrays $a$ are permutations of $[1, 2, 3, 4, 5, 6]$. Since each array $a$ will have $f(a) = 0$, so maximum value is $f(a) = 0$ and there are $6! = 720$ such arrays.

In the second example, the only possible array consists of $10^6$ ones and its $f(a) = \sum\limits_{1 \le i \lt j \le 10^6}{j - i} = 166\,666\,666\,666\,500\,000$ and $166\,666\,666\,666\,500\,000 \bmod{10^9 + 7} = 499\,833\,345$.

在第一个例子中，所有可能的数组 $a$ 都是 $[1, 2, 3, 4, 5, 6]$ 的排列。由于每个数组 $a$ 均满足 $f(a) = 0$，因此 $f(a)$ 的最大值为 $0$，且这样的数组共有 $6! = 720$ 个。

在第二个例子中，唯一可能的数组由 $10^6$ 个 $1$ 组成，其 $f(a) = \sum\limits_{1 \le i \lt j \le 10^6}{j - i} = 166\,666\,666\,666\,500\,000$，且 $166\,666\,666\,666\,500\,000 \bmod{10^9 + 7} = 499\,833\,345$。