CF396D.On Sum of Number of Inversions in Permutations

You are given a permutation p. Calculate the total number of inversions in all permutations that lexicographically do not exceed the given one.

As this number can be very large, print it modulo 1000000007 (109 + 7).

给你一个排列 $p$。请计算所有字典序不大于该排列的排列中逆序对的总数。

由于该数可能非常大，请输出其对 $1000000007$（即 $10^9 + 7$）取模的结果。

The first line contains a single integer n (1 ≤ n ≤ 106) — the length of the permutation. The second line contains n distinct integers _p_1, _p_2, ..., p__n (1 ≤ p__i ≤ n).

第一行包含一个整数 $n$（$1 \leq n \leq 10^6$）—— 排列的长度。
第二行包含 $n$ 个互不相同的整数 $p_1, p_2, \ldots, p_n$（$1 \leq p_i \leq n$）。

Print a single number — the answer to the problem modulo 1000000007 (109 + 7).

输出一个数字——该问题答案对 1000000007（$10^9 + 7$）取模的结果。

Permutation p of length n is the sequence that consists of n distinct integers, each of them is from 1 to n.

An inversion of permutation _p_1, _p_2, ..., p__n is a pair of indexes (i, j), such that i < j and p__i > p__j.

Permutation a do not exceed permutation b lexicographically, if either a = b or there exists such number i, for which the following logical condition fulfills: AND (a__i < b__i).

长度为 $n$ 的排列 $p$ 是由 $n$ 个互不相同的整数组成的序列，且每个整数均在 $1$ 到 $n$ 之间。

排列 $p_1,\,p_2,\,\dots,\,p_n$ 的一个逆序对是指满足 $i < j$ 且 $p_i > p_j$ 的下标对 $(i,\,j)$。

排列 $a$ 在字典序上不大于排列 $b$，当且仅当 $a = b$，或者存在某个下标 $i$，使得以下逻辑条件成立： 且 $a_i < b_i$。