2134

Task

Given a permutation $P = [P_0, P_1, \ldots, P_{N-1}]$ of length $N$, count the number of tuples $0 \leq a < b < c < d < N$, where $P_b < P_a < P_c < P_d$. Since the answer can be large, print its remainder modulo $10^9 + 7$.

Input data

The input file consists of:

• a line containing integer $N$.
• a line containing the $N$ integers $P_{0}, \, \ldots, \, P_{N-1}$.

Output data

The output file must contain a single line consisting of integer $K$ -- the number of such tuples modulo $10^9+7$.

Constraints and clarifications

• $1 \le N \le 500 \ 000$.
• $1 \le P_i \le N$ for each $i=0\ldots N-1$.
• $P_i \neq P_j$ for every $0\leq i < j < N$.

Example 1

stdin

5
2 1 3 4 5

stdout

3

Explanation

In the first sample case the following tuples meet the requirements: $(0, 1, 2, 3)$, $(0, 1, 2, 4)$, $(0, 1, 3, 4)$.

Example 2

stdin

10
4 5 1 2 8 7 9 3 6 10

stdout

27