1920. Номер перестановки

Перестановкой из `N` элементов называется упорядоченный набор из `N` различных чисел от 1 до `N`. Количество всех перестановок из `N` элементов равно `N!\ =\ 1\ *\ 2\ *\ 3\ *\ …\ *\ N`. Требуется найти номер заданной перестановки в лексикографическом порядке. Например, для `N=3` лексикографический порядок перестановок выглядит следующим образом:

(1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1).

Таким образом, перестановка (3,1,2) имеет номер 5 в этой последовательности.

В первой строке входного файла записано число `N` (`1\ ≤\ N\ ≤\ 100000`) — количество элементов в перестановке. Во второй строке даны `N` целых чисел — элементы данной перестановки.

В выходной файл выведите единственное целое число — номер данной перестановки в лексикографическом порядке. Так как это число может быть очень большим выведите остаток от его деления на 1000000007 (`10^9+7`).

3
3 1 2

5

4
2 3 1 4

9