排列计数(Permutation Count)

题目描述

给定 a₁,a₂,…,aₙ，它是一个 1 到 n 的排列，也就是说，a₁ 到 aₙ 这些数字互不相同且都是在 1 到 n 之间的整数。若将所有 1 到 n 的排列按照字典序列出，请求出 a₁,a₂,…,aₙ 在其中的名次。

如 n=3 时，所有排列为（按字典序罗列）：

1, 2, 3 1, 3, 2 2, 1, 3 2, 3, 1 3, 1, 2 3, 2, 1

其中 3, 1, 2 的名次为 5。

序列的字典序是指定义两个序列大小的一种方法。设有两个序列 x₁,x₂,…,xₙ 与 y₁,y₂,…,yₙ，若 x₁ 与 y₁ 能够区分大小，则以它们的大小定义 x 序列与 y 序列的大小；否则，以 x₂ 与 y₂ 定义两序列的大小，若 x₂ 与 y₂ 仍一样大，则以 x₃ 与 y₃ 区分，以此类推，直到 xₙ 与 yₙ。

输入格式

• 第一行：单个整数表示 N；
• 第二行：N 个整数表示 A₁,A₂,…,Aₙ。

输出格式

• 单个整数：表示输入排列在所有排列中的名次，由于数字可能很大，取答案模 1,000,000,007 的余数。

数据范围

• 对于 40% 的分数，1 ≤ n ≤ 10；
• 对于 70% 的分数，1 ≤ n ≤ 10,000；
• 对于 100% 的分数，1 ≤ n ≤ 200,000。

样例输入 #1

3
3 1 2

样例输出 #1

5

样例输入 #2

4
4 3 2 1

样例输出 #2

24

样例2说明：所有排列中的最后一个排列。

知识点与难度

本题涉及的知识点从属于 GESP 5级，难度等级：⭐⭐⭐。

测试点分布