No tag edit access

D. On Sum of Number of Inversions in Permutations

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou 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).

Examples

Input

2

2 1

Output

1

Input

3

2 1 3

Output

2

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

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/23/2017 09:59:51 (p1).

Desktop version, switch to mobile version.
User lists

Name |
---|