Перестановкой длины \(n\) является массив, состоящий из \(n\) различных целых чисел от \(1\) до \(n\) в произвольном порядке. Например, \([2,3,1,5,4]\) — перестановка, но \([1,2,2]\) не перестановка (\(2\) встречается в массиве дважды) и \([1,3,4]\) тоже не перестановка (\(n=3\), но в массиве встречается \(4\)). Всего существует \(n! = n \cdot (n-1) \cdot (n - 2) \cdot \ldots \cdot 1\) различных перестановок длины \(n\).
По произвольной перестановке \(p\) длины \(n\) мы создаем массив \(a\) длины \(2n\), который равен конкатенации \(p\) и ее разворота. Далее, стоимостью \(p\) назовем число инверсий в \(a\).
Число инверсий в массиве \(a\) определяется как количество пар индексов \(i\), \(j\), таких что \(i < j\) и \(a_i > a_j\).
Например, если \(p = [1, 2]\), то \(a\) будет равно \([1, 2, 2, 1]\). В \(a\) всего две инверсии: \((2, 4)\) и \((3, 4)\) (нумерация элементов с 1). Значит, стоимость \(p\) равна \(2\).
Ваша задача — найти сумму стоимостей всех \(n!\) перестановок длины \(n\). Выведите остаток от деления этой суммы на \(1\,000\,000\,007\) (\(10^9 + 7\)).
Выходные данные
Для каждого набора входных данных выведите одно число — сумму стоимостей всех перестановок длины \(n\) по модулю \(1\,000\,000\,007\) (\(10^9 + 7\)).
Примечание
В первом наборе входных данных \(p = [1]\) — единственная возможная перестановка. Тогда \(a = [1, 1]\), и в этом массиве \(0\) инверсий.
Во втором наборе входных данных перестановки — это \([1, 2]\) и \([2, 1]\). Их соответствующие массивы \(a\) таковы: \([1, 2, 2, 1]\) и \([2, 1, 1, 2]\). В них обоих по \(2\) инверсии.