题目描述

给定 $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$ 的余数。

3
3 1 2

5

4
4 3 2 1

24

样例解释 2

所有排列中的最后一个排列

数据范围

• 对于 $40\%$ 的分数，$1\leq n\leq 10$；
• 对于 $70\%$ 的分数，$1\leq n\leq 10000$；
• 对于 $100\%$ 的分数，$1\leq n\leq 200000$。