Задан массив a, состоящий из n элементов. Определим fa следующим образом:
- Изначально fa = 0, M = 1;
- для каждого 2 ≤ i ≤ n если aM < ai, то установим fa = fa + aM и M = i.
Посчитайте сумму fa по всем n! перестановкам массива a по модулю 109 + 7.
Обратите внимание, что два элемента считаются различными, если различаются их позиции, поэтому у любого массива a есть ровно n! перестановок.
Выходные данные
Выведите одно целое число, сумму fa по всем n! перестановкам массива a по модулю 109 + 7.
Примечание
Перестановки во втором примере:
- 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.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
1 3
|
1
|
|
2
|
3
1 1 2
|
4
|