Bad Hair Day and Expected Value

Farmer John has N cows. Their heights vary, and two cows may have the same height.

The cows dislike their hairstyles, so they line up to check each other's hairstyles.

Each cow looks to her right and can check the hairstyles of all cows that appear before a cow at least as tall as herself shows up. More precisely, if the height of the cow standing at position i from the left is *H'*i, then cow i can see cow j when, and only when, the following conditions hold.

• i < j and *H'*i > *H'*j.
• There is no k with i < k < j and *H'*i ≤ *H'*k.

Since there are N cows, the number of ways they can line up is N!. Farmer John wants to know the expected number of pairs of cows that can check each other's hairstyles. Write a program that helps Farmer John print this expected value.

The first line gives N, a positive integer that indicates the number of cows.

The second line gives N positive integers H1, ..., HN, the heights of the N cows, separated by spaces.

Suppose two coprime nonnegative integers $P$ and $Q$ satisfy that the expected number of pairs of cows that can check each other's hairstyles equals $\displaystyle \frac{P}{Q}$. Find the integer $X$ with $0 \le X < (10^{9} + 7)$ such that $P \equiv QX \pmod{10^{9} + 7}$, and print it on the first line.

There always exist $P$, $Q$, and $X$ that satisfy the conditions. $X$ is also guaranteed to be unique.

Every input satisfies the following conditions.

• 1 ≤ N ≤ 2 × 105
• 1 ≤ Hi ≤ 109 (1 ≤ i ≤ N)