Вам задан массив \(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)\). Два массива считаются различными, если элементы в какой-то позиции различаются.
Выходные данные
Выведите два целых числа — максимально возможное \(f(a)\) и количество массивов \(a\) с данным значением. Так как оба ответа могут быть очень большими, выведите их по модулю \(10^9 + 7\).
Примечание
В первом примере, все возможные массивы \(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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
1 1 1 1 1 1
|
0 720
|
|
2
|
1
1000000
|
499833345 1
|
|
3
|
7
123 451 234 512 345 123 451
|
339854850 882811119
|