G. Массив максимальной суммы
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам задан массив $$$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)$$$ и количество массивов с данным значением $$$f(a)$$$. Два массива считаются различными, если элементы в какой-то позиции различаются.

Входные данные

В первой строке задано одно целое число $$$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$$$.

Выходные данные

Выведите два целых числа — максимально возможное $$$f(a)$$$ и количество массивов $$$a$$$ с данным значением. Так как оба ответа могут быть очень большими, выведите их по модулю $$$10^9 + 7$$$.

Примеры
Входные данные
6
1 1 1 1 1 1
Выходные данные
0 720
Входные данные
1
1000000
Выходные данные
499833345 1
Входные данные
7
123 451 234 512 345 123 451
Выходные данные
339854850 882811119
Примечание

В первом примере, все возможные массивы $$$a$$$ — это перестановки $$$[1, 2, 3, 4, 5, 6]$$$. Так как у каждого такого $$$a$$$ значение $$$f(a) = 0$$$, то максимально возможное $$$f(a) = 0$$$ и количество таких массивов равно $$$6! = 720$$$.

Во втором примере, единственный возможный массив состоит из $$$10^6$$$ единиц и его $$$f(a) = \sum\limits_{1 \le i < 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$$$.