题目描述
给定 $a_1,a_2,\dots,a_n$，它是一个 $1$ 到 $n$ 的**排列**，也就是说，$a_1$ 到 $a_n$ 这些数字互不相同且都是在 $1$ 到 $n$ 之间的整数。若将所有 $1$ 到 $n$ 的**排列**按照字典序列出，请求出 $a_1,a_2,\dots,a_n$ 在其中的名次。
如 $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_1,x_2,\dots,x_n$ 与 $y_1,y_2,\dots,y_n$，若 $x_1$ 与 $y_1$ 能够区分大小，则以它们的大小定义 $x$ 序列与 $y$ 序列的大小；否则，以 $x_2$ 与 $y_2$ 定义两序列的大小，若 $x_2$ 与 $y_2$ 仍一样大，则以 $x_3$ 与 $y_3$ 区分，以此类推，直到 $x_n$ 与 $y_n$。
输入
第一行：单个正整数表示 $n$；
第二行：$n$ 个正整数表示 $a_1,a_2,\dots,a_n$。
输出
单个整数：表示输入排列在所有排列中的名次，由于数字可能很大，取答案模 $10^9+7$ 的余数。
样例输入输出
提示
+ 对于 $40\%$ 的分数，$1\leq n\leq 10$；
+ 对于 $70\%$ 的分数，$1\leq n\leq 10000$；
+ 对于 $100\%$ 的分数，$1\leq n\leq 200000$。
样例2说明:所有排列中的最后一个排列