Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

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-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/19/2018 16:30:42 (d2).

Desktop version, switch to mobile version.

User lists

Name |
---|