Problem Description

You are given a permutation $ P = p_1, p_2, ..., p_N $ of length $ N $. For all permutations of length $ N $ that are lexicographically less than or equal to $ P $, calculate the inversion count and output the sum of these inversion counts. Since the answer can be very large, output it modulo $ 10^9 + 7 $.

The inversion count of a permutation $ X = x_1, x_2, ..., x_N $ is the number of pairs of integers $ (i, j) $ such that $1 \leq i < j \leq N$ and $ x_i > x_j $.

Input Format

The input is given from the standard input in the following format:

$ N $ $ p_1 $ $ p_2 $ $ ... $ $ p_N $

Output Format

For all permutations of length $ N $ that are lexicographically less than or equal to the permutation $ P $, calculate the inversion count and output the sum of these inversion counts modulo $ 10^9 + 7 $.

Sample Input and Output

Sample Input #1

3
2 1 3

Sample Output #1

2

Sample Input #2

4
1 2 3 4

Sample Output #2

0

Sample Input #3

8
5 6 2 7 1 3 8 4

Sample Output #3

281881

Notes/Hints

Constraints

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq p_i \leq N$
• All inputs are integers.
• $ p_1, p_2, ..., p_N $ is a permutation.

Sample Explanation 1

The permutations of length 3 that are lexicographically less than or equal to $ (2, 1, 3) $ are $ (1, 2, 3) $, $ (1, 3, 2) $, and $ (2, 1, 3) $. The inversion counts of these permutations are 0, 1, and 1 respectively, so the answer is $ 0 + 1 + 1 = 2 $.

见题面 Input 部分

见题面 Output 部分