题目描述

题目译自 XXIII Olimpiada Informatyczna — III etap Pracowity Jaś

今天是小 Johny 的生日……但这是一道严肃的算法题，可怜的 Johny 没有收到玩具、游戏或电脑作为礼物。相反，他得到了一堆充满数字的长数组、树形结构、遍布隧道和立交桥的奇异地图，以及长达 1048576 个符号的 Fibonacci 和 Thue-Morse 序列前缀等教育礼物。在这些礼物中，他最喜欢的是一个包含 $1$ 到 $n$ 的正整数排列的数组。很快，Johny 开始思考这个排列的字典序前驱排列†是什么。聪明如他，很快解决了这个问题，并立即想到如何通过数组支持的唯一操作——交换任意两个单元的内容——将当前排列转换为其前驱。Johny 发现这个任务如此引人入胜，以至于他不断将每个排列转换为其字典序前驱。

沉迷于排列变换的 Johny 完全忽略了生日派对的宾客。宾客们觉得这既有趣又有些失礼。很快，有人意识到 Johny 会在达到字典序最小的单位排列 $1,2,\ldots,n$ 时停下来。问题在于，这需要多长时间？请帮助宾客们解答这个问题，假设每次交换耗时一秒。由于 Johny 极其勤奋，这个过程可能很长，宾客们只关心交换次数对 $10^9+7$ 取模的结果。他们可以每隔 $10^9+7$ 秒检查一次，看 Johny 是否终于完成了。

输入格式

第一行包含一个正整数 $n$，表示 Johny 收到的排列长度。

第二行包含 $n$ 个互不相同的整数 $p_1, p_2, \ldots, p_n$ $(1 \leq p_i \leq n)$，表示排列的元素。

输出格式

输出一行，包含一个整数，表示 Johny 停止前进行的交换次数对 $10^9+7$ 取模的结果。

3
3 1 2

6

Johny 经历的字典序递减排列序列为 $(3,1,2), (2,3,1), (2,1,3), (1,3,2), (1,2,3)$。为此，他总共进行了 $2+1+2+1=6$ 次交换。

附加样例

1. $n=10$，排列为 $1,2,3,\ldots,10$。
2. $n=5$，一个随机 $5$ 元素的排列。
3. $n=100$，排列为 $100,99,98,\ldots,1$。

数据范围与提示

详细子任务附加限制及分值如下表所示。