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).
输入描述:
The first line contains a single integer n (1 ≤ n ≤ 106) — the length of the permutation. The second line contains n distinct integers p1, p2, ..., pn (1 ≤ pi ≤ n).
输出描述:
Print a single number — the answer to the problem modulo 1000000007(109 + 7).
示例1
输入
2<br />2 1<br />3<br />2 1 3<br />
备注:
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 p1, p2, ..., pn is a pair of indexes (i, j), such that i j and pi pj.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 (ai bi).
加载中...