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$ $(10^{9} + 7)$.

Input

The first line contains a single integer $*n*$ ($1 ≤ *n* ≤ 10^{6}$) — the length of the permutation. The second line contains $*n*$ distinct integers $*p*_{1}, *p*_{2}, ..., *p*_{*n*}$ ($1 ≤ *p*_{*i*} ≤ *n*$).

Output

Print a single number — the answer to the problem modulo $1000000007$ $(10^{9} + 7)$.

Note

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*})$.