시간 제한메모리 제한제출정답맞은 사람정답 비율
1 초 256 MB0000.000%

문제

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

예제 입력 1

5
1 2 3 4 5

예제 출력 1

0

예제 입력 2

5
1 2 5 3 4

예제 출력 2

3