问题背景

我们称一个长度为 $n$ 的数列是一个排列，当且仅当整数 $1, 2, \ldots, n$ 在排列中均恰好出现一次。比如：

• 数列 $\{ 1, 3, 2 \}$，$\{ 5, 3, 1, 4, 2, 6 \}$ 都是排列；
• 数列 $\{ 1, 1, 2 \}$，$\{ 1, 2, 4, 3, 6 \}$ 都不是排列。

题目描述

给你一个长度为 $n$ 的排列 $p_1, p_2, \ldots, p_n$，求这个排列是第几个排列。由于这个数字可能很大，所以你只需要输出其 $\text{ mod } 10^9+7$ 的结果即可。

说明：长度为 $n$ 的排列一共有 $n!$ 个。当 $n = 3$ 时，一共有 $3! = 6$ 个不同的排列：

• 排列 $\{ 1, 2, 3 \}$ 是第 $1$ 个排列；
• 排列 $\{ 1, 3, 2 \}$ 是第 $2$ 个排列；
• 排列 $\{ 2, 1, 3 \}$ 是第 $3$ 个排列；
• 排列 $\{ 2, 3, 1 \}$ 是第 $4$ 个排列；
• 排列 $\{ 3, 1, 2 \}$ 是第 $5$ 个排列；
• 排列 $\{ 3, 2, 1 \}$ 是第 $6$ 个排列。

输入格式

第一行，一个整数 $n(1 \le n \le 10^5)$。

第二行，$n$ 个整数 $p_1, p_2, \ldots, p_n$，表示一个长度为 $n$ 的排列。

输出格式

输出一个整数，表示排列 $p$ 是所有长度为 $n$ 的排列中的第几个排列，数字对 $10^9 + 7$ 取模。

样例

3
1 3 2

2

8
5 8 1 4 6 3 2 7

24543

说明/提示

数据规模与约定

• 对于 $20\%$ 的数据，$n \le 10$
• 对于 $50\%$ 的数据，$n \le 1000$
• 对于 $100\%$ 的数据，$1 \le n \le 10^5$，且数列 $p_1, p_2, \ldots, p_n$ 是一个大小为 $n$ 的排列