23138번 - Swapping Inversions 다국어

문제

You are given a permutation $x$ of the integers from 1ドル$ to $n$.

You want to sort this permutation by a sequence of operations. In one operation, you select two adjacent elements $x_i$ and $x_{i+1}$ such that $x_i > x_{i+1}$ and swap them. When there are multiple choices of such $i,ドル you choose one of them with equal probability. When there is no such $i,ドル the process ends.

The cost of swapping $x_i$ and $x_{i+1}$ is $|x_i - x_{i+1}|$. Calculate the expected total cost of sorting the permutation modulo 10ドル^9 + 7$.

입력

The first line of input contains an integer $n$ (1ドル \leq n \leq 10^6$).

The second line contains $n$ integers $x_1, x_2, \ldots, x_n$ (1ドル \leq x_i \leq n$). It is guaranteed that $x$ is a permutation of the integers from 1ドル$ to $n$.

출력

Print a single line containing an integer: the expected total cost modulo 10ドル^9 + 7$.

Formally, it can be shown that the expected total cost can be represented as a fraction $p / q$ for some coprime non-negative integers $p$ and $q$. For example, if the expected total cost is an integer, then we just have $q = 1$. You have to print the value $p \cdot q^{-1} \bmod (10^9 + 7)$.

제한

힌트