P11319 [NOISG 2020 Qualification] Cryptography

Charles 是一位密码学家，他正在研究生成随机数的新方法。他试图通过组合多个随机数源来创建一个密码学安全的伪随机数生成器（CSPRNG）。

他发明了一种算法，包括以下步骤： 1. 随机生成一个长度为 $N$ 的正整数序列 $S$，其中元素两两不同。 2. 随机打乱 $S$，得到一个长度为 $N$ 的排列 $P$。 3. 计算排列 $P$ 的字典序排名。 4. 输出排名对 $10^9 + 7$ 取模的结果。 排列 $P$ 的字典序排名定义为所有小于等于 $P$ 的排列数量。 Charles 是一位密码学家，但不是程序员。现在，给定排列 $P$，请帮助 Charles 计算其字典序排名，并对 $10^9 + 7$ 取模。

第一行包含一个整数 $N$，表示排列的长度。 第二行包含 $N$ 个正整数 $P_1, P_2, \dots, P_N$，表示排列 $P$。

输出一个整数，表示排列 $P$ 的字典序排名，对 $10^9 + 7$ 取模。

【样例解释】 对于样例 #1，以下是所有排列的字典序： 1. $[1, 42, 100]$ 2. $[1, 100, 42]$ 3. $[42, 1, 100]$ 4. $[42, 100, 1]$ 5. $[100, 1, 42]$ 6. $[100, 42, 1]$ 排列 $[42, 100, 1]$ 的字典序排名为 $4$。 【数据范围】 - $1 \leq N \leq 3 \times 10^5$ - $1 \leq P_i \leq 10^9$ - 对于任意 $i \neq j$，$P_i \neq P_j$ | 子任务编号 | 分值 | 限制条件 | |:--------:|:---------:|:--------------------------------------------------:| | $1$ | $5$ | $N = 2$ | | $2$ | $9$ | $1 \leq N \leq 8$ | | $3$ | $10$ | $P$ 为严格递增或递减 | | $4$ | $11$ | $P = [k, 1, \dots, k-1, k+1, \dots, N]$，$1 \leq k \leq N$ | | $5$ | $21$ | $1 \leq N \leq 3 \times 10^3, 1 \leq P_i \leq N$ | | $6$ | $13$ | $1 \leq N \leq 3 \times 10^3$ | | $7$ | $19$ | $1 \leq P_i \leq N$ | | $8$ | $12$ | 无其他特殊限制 |