Вам задан массив $$$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$$$.
