题目描述
题目描述
给定a1,a2,…,an，它是一个1 到n 的排列，也就是说，a1到 an 这些数字互不相同且都是在 1到 n之间的整数。若将所有 1到 n的排列按照字典序列出，请求出 a1,a2,…,an在其中的名次。
如 n=3时，所有排列为（按字典序罗列）：
1, 2, 3
1, 3, 2
2, 1, 3
2, 3, 1
3, 1, 2
3, 2, 1
其中 3, 1, 2 的名次为 5。
序列的字典序是指定义两个序列大小的一种方法。设有两个序列x1,x2,...xn与 y1,y2,…,yn，若x1与y1能够区分大小，则以它们的大小定义 x序列与 y序列的大小；否则，以x2与y2定义两序列的大小，若x2与y2仍一样大，则以 x3与y3区分，以此类推，直到 xn与 yn。
输入格式
第一行：单个正整数表示 n；
第二行：n 个正整数表示 a1,a2,…,an。
输出格式
单个整数：表示输入排列在所有排列中的名次，由于数字可能很大，取答案模 109+7的余数。
数据范围
对于 40% 的分数，1≤n≤10；
对于 70% 的分数，1≤n≤10000；
对于 100% 的分数，1≤n≤200000。
样例数据
输入:
3
3 1 2
输出:
5
输入:
4
4 3 2 1
输出:
24
说明:
所有排列中的最后一个排列
样例输入 复制
样例输出 复制