E. История максимумов
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Задан массив a, состоящий из n элементов. Определим fa следующим образом:

  • Изначально fa = 0, M = 1;
  • для каждого 2 ≤ i ≤ n если aM < ai, то установим fa = fa + aM и M = i.

Посчитайте сумму fa по всем n! перестановкам массива a по модулю 109 + 7.

Обратите внимание, что два элемента считаются различными, если различаются их позиции, поэтому у любого массива a есть ровно n! перестановок.

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

В первой строке записано целое число n (1 ≤ n ≤  1 000 000) — размер массива a.

Во второй строке записаны n целых чисел a1, a2, ..., an (1 ≤  ai ≤  109).

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

Выведите одно целое число, сумму fa по всем n! перестановкам массива a по модулю 109 + 7.

Примеры
Входные данные
2
1 3
Выходные данные
1
Входные данные
3
1 1 2
Выходные данные
4
Примечание

Перестановки во втором примере:

  • p = [1, 2, 3] : fa равно 1;
  • p = [1, 3, 2] : fa равно 1;
  • p = [2, 1, 3] : fa равно 1;
  • p = [2, 3, 1] : fa равно 1;
  • p = [3, 1, 2] : fa равно 0;
  • p = [3, 2, 1] : fa равно 0.

Где p — массив позиций оригинального массива a. Сумма fa равна 4.