У Сакурако есть коробка, в которой \(n\) мячей. Каждый мяч имеет свою стоимость. Она хочет поспорить со своим другом, что если он наугад выберет из коробки два мяча (это могут быть два разных мяча, но они могут иметь одинаковое значение), то произведение их значений будет равно числу, которое загадала Сакурако.
Так как Сакурако имеет докторскую степень по теории вероятностей, она знает, что наилучшее число для выбора — это математическое ожидание, но она забыла, как его вычислить. Помогите Сакурако и найдите математическое ожидание произведения двух элементов из массива.
Можно показать, что математическое ожидание имеет вид \(\frac{P}{Q}\), где \(P\) и \(Q\) — неотрицательные целые числа, а \(Q \ne 0\). Сообщите значение \(P \cdot Q^{-1}(\bmod 10^9+7)\).
Выходные данные
Для каждого набора входных данных выведите значение \(P \cdot Q^{-1}(\bmod 10^9+7)\).
Примечание
Для первого теста друг Сакурако может выбрать такие пары шаров: \((a_1,a_2)\), \((a_1,a_3)\), \((a_2,a_3)\). Их произведение равно \(3\cdot 2=6\), \(3\cdot 3=9\), \(3\cdot 2=6\) соответственно, поэтому математическое ожидание равно \(\frac{6+9+6}{3}=7\).
Для второго теста друг Сакурако может выбрать такие пары шаров: \((a_1,a_2)\), \((a_1,a_3)\), \((a_1,a_4)\), \((a_2,a_3)\), \((a_2,a_4)\), \((a_3,a_4)\). Их произведение равно \(2\cdot 2=4\), \(2\cdot 2=4\), \(2\cdot 4=8\), \(2\cdot 2=4\), \(2\cdot 4=8\), \(2\cdot 4=8\) соответственно, поэтому математическое ожидание равно \(\frac{4+4+8+4+8+8}{6}=\frac{36}{6}=6\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3
3 2 3
4
2 2 2 4
5
1 2 3 4 5
|
7
6
500000012
|