给定一个 $1$ 到 $n$ 的排列 $x$。

你希望通过一系列操作将该排列排序。在一次操作中，你选择两个相邻的元素 $x_i$ 和 $x_{i+1}$，满足 $x_i > x_{i+1}$，并将它们交换。当存在多个这样的 $i$ 时，你以相等的概率选择其中一个。当不存在这样的 $i$ 时，过程结束。

交换 $x_i$ 和 $x_{i+1}$ 的代价为 $|x_i - x_{i+1}|$。计算排序该排列的总代价的期望值，结果对 $10^9 + 7$ 取模。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 10^6$)。

第二行包含 $n$ 个整数 $x_1, x_2, \dots, x_n$ ($1 \le x_i \le n$)。保证 $x$ 是 $1$ 到 $n$ 的一个排列。

输出格式

输出一行，包含一个整数：总代价的期望值对 $10^9 + 7$ 取模的结果。

形式化地，可以证明期望总代价可以表示为一个分数 $p/q$，其中 $p$ 和 $q$ 是互质的非负整数。例如，如果期望总代价是一个整数，则 $q = 1$。你需要输出 $p \cdot q^{-1} \pmod{10^9 + 7}$ 的值。

样例

样例输入 1

5
1 2 3 4 5

样例输出 1

0

样例输入 2

5
1 2 5 3 4

样例输出 2

3