You are given a permutation (p_1, p_2, \ldots, p_n) of the numbers from to .
You can perform the following operation with it:
You can swap two adjacent elements of . This operation takes exactly one second.
In one iteration you do the following:
Consider the permutation (q_1, q_2, \ldots, q_n) that comes immediately before (p_1, p_2, \ldots, p_n) in lexicographic order, that is, is lexicographically smaller than and there is no permutation "between them". For example, for p = (2, 3, 1) we have q = (2, 1, 3), for p = (3, 1, 2, 4) we have q = (2, 4, 3, 1), and for p = (1, 4, 2, 3) we have q = (1, 3, 4, 2).
Transform the permutation into the permutation using the minimum possible number of operations. For example, to transform (1, 4, 2, 3) into (1, 3, 4, 2), at least operations are needed: (1, 4, 2, 3) \to (1, 4, 3, 2) \to (1, 3, 4, 2).
You apply this iteration to the resulting permutation until it becomes the identity permutation (that is, equal to (1, 2, 3, \ldots, n)). How much time will this take? Since this number can be very large, print it modulo 10^9+7.
A permutation is considered lexicographically smaller than a permutation if there is an index such that p_j = q_j for all j<i, and p_i<q_i.
The first line contains one integer (1 \le n \le 2\cdot 10^5) — the length of the permutation.
The second line contains integers p_1, p_2, \ldots, p_n (1 \le p_i \le n, all numbers are pairwise distinct) — the elements of the permutation.
Print the number of seconds that will pass until the process ends, modulo 10^9+7.
Example 1
Example 2
In the first sample we have:
(1, 4, 2, 3) \to (1, 4, 3, 2) \to (1, 3, 4, 2): seconds.
(1, 3, 4, 2) \to (1, 3, 2, 4): second.
(1, 3, 2, 4) \to (1, 2, 3, 4) \to (1, 2, 4, 3): seconds.
(1, 2, 4, 3) \to (1, 2, 3, 4): second.
seconds in total.