小约翰过生日了……但这可是一个严肃的算法问题，所以这个可怜的孩子没收到任何玩具、游戏或电脑作为生日礼物。相反，他收到了一些填满数字的长数组、树、地图，以及写满长达 $1048576$ 个字符的斐波那契数列和图厄-莫尔斯序列（Thue-Morse words）前缀的磁带等等。在所有这些益智礼物中，他最喜欢的是一个包含前 $n$ 个正整数的排列*的数组。很快，小约翰开始好奇他所得到的排列的字典序前驱排列†是什么。在很快算出答案后，小约翰立刻问自己，如何在数组中写出这个前驱排列。数组唯一支持的操作是交换任意两个单元格的内容。幸运的是，小约翰足够聪明，能以最少的交换次数将初始排列转换为其前驱排列。他发现这个任务非常引人入胜，于是他不断地将每一个后续的排列转换为它的前驱排列。
在沉迷于排列的过程中，小约翰忽略了他所有的生日派对客人，客人们觉得这很有趣，但也有些失礼。其中一位客人很快意识到，当小约翰得到字典序最小的恒等排列 $1, 2, \dots, n$ 时，他就会停止。问题是，这需要多长时间？请帮助他们回答这个问题，已知每次交换都需要小约翰正好一秒钟。由于这可能需要一段时间（“勤奋”是小约翰的中间名），客人们只要知道总时间对 $10^9 + 7$ 取模的结果就心满意足了。毕竟，他们每隔 $10^9 + 7$ 秒就可以检查一下小约翰是否终于完成了。
输入格式
标准输入的第一行包含一个正整数 $n$，表示小约翰得到的排列的长度。第二行给出了该排列，为一个包含 $n$ 个互不相同的整数 $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$) 的序列，由空格分隔。
输出格式
你的程序应向标准输出打印小约翰在停止前所进行的交换次数对 $10^9 + 7$ 取模的结果。
样例
样例输入 1
3 3 1 2
样例输出 1
6
说明
小约翰所经历的字典序递减的排列序列为 $(2, 3, 1), (2, 1, 3), (1, 3, 2), (1, 2, 3)$。为了得到这些排列，他总共进行了 $2 + 1 + 2 + 1 = 6$ 次交换。
子任务
测试集由以下子任务组成。每个子任务内可能包含多个测试组。
| 子任务 | 属性 | 分值 |
|---|---|---|
| 1 | $n \le 10$ | 15 |
| 2 | $n \le 5000$ | 37 |
| 3 | $n \le 1\,000\,000$，排列为 $n, n-1, \dots, 1$ | 15 |
| 4 | $n \le 1\,000\,000$ | 33 |
- $1$ 到 $n$ 的数字的排列是一个由互不相同的整数 $p_1, \dots, p_n$ 组成的序列，满足 $1 \le p_i \le n$（即 $1$ 到 $n$ 的每个整数在排列中恰好出现一次）。 † 排列 $P = (p_1, \dots, p_n)$ 的字典序小于排列 $Q = (q_1, \dots, q_n)$（记作 $P < Q$），如果存在索引 $j$ 使得 $p_j < q_j$，且对于所有小于 $j$ 的索引 $k$ 都有 $p_k = q_k$。如果 $P < Q$ 且不存在排列 $R$ 使得 $P < R < Q$，则称排列 $P$ 是 $Q$ 的字典序前驱。