Lexicographical Rank of a Permutation

Given a permutation \(P\) of distinct positive integers, compute its lexicographical rank. The rank is defined as the number of permutations which are lexicographically less than or equal to \(P\). Since the result can be very large, output the answer modulo \(10^9+7\).

For a permutation \(P = [P_1, P_2, \ldots, P_N]\), the rank can be computed as follows:

\[ \text{rank} = 1 + \sum_{i=1}^{N} \text{count}_i \times (N-i)! \mod (10^9+7) \]

where \(\text{count}_i\) is the number of unused numbers smaller than \(P_i\) at the \(i\)th step. The ranking starts from 1.

inputFormat

The first line contains a single integer (N) ((1 \le N \le 10^5)). The second line contains (N) distinct positive integers representing the permutation (P).

outputFormat

Output a single integer: the lexicographical rank of the permutation modulo (10^9+7).

sample

3
1 2 3

1