D. О сумме количества инверсий в перестановках
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Вам дана перестановка p. Посчитайте суммарное количество инверсий во всех перестановках, лексикографически не больших данной.

Поскольку это число может быть очень большим, выведите его по модулю 1000000007 (109 + 7).

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

В первой строке задано единственное целое число n (1 ≤ n ≤ 106) — длина перестановки. Во второй строке заданы n различных целых чисел p1, p2, ..., pn (1 ≤ pi ≤ n).

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

Выведите единственное число — ответ на задачу по модулю 1000000007 (109 + 7).

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

Перестановкой p длины n называется последовательность, состоящая из n различных целых чисел, каждое из которых от 1 до n.

Инверсией перестановки p1, p2, ..., pn называется пара индексов (i, j), такая что i < j и pi > pj.

Перестановка a лексикографически не больше перестановки b, если a = b или существует такое число i, для которого выполняется логическое условие: И (ai < bi).