题目描述

给定 $1 \sim n$ 的排列 $a_{[1, n]}$。在上面进行一次如下操作：

1. 首先在 中选取一个子序列（可以为空）；
2. 然后将这个子序列内的数重新排列。

两个操作不同，当且仅当选取的子序列不同或者重新排列的方式不同。

对所有不同的操作，求它们产生的排列的逆序对个数和，模 $10^9 + 7$。

输入格式

第一行一个整数 $n$。 接下来一行 $n$ 个数，表示排列 $a$。

输出格式

一行一个整数表示答案。

样例 #1

样例输入 #1

2
1 2

样例输出 #1

1

样例 #2

样例输入 #2

3
3 1 2

样例输出 #2

28

样例 #3

见下发文件

提示

样例 1：

• 选择空子序列，产生 $1, 2$。
• 选择 $1$，产生 $1, 2$。
• 选择 $2$，产生 $1, 2$。
• 选择 $1, 2$ 并打乱为 $1, 2$，产生 $1, 2$。
• 选择 $1, 2$ 并打乱为 $2, 1$，产生 $2, 1$。
• 答案为 $1$。

样例 2：

• 注意子序列可以不连续。

数据范围：

对于所有数据，满足 $2 \leq n \leq 5 \times 10^5$，保证输入序列是一个排列。

下发文件