When There Is Nothing to Do and Only a Permutation at Home#12857

When There Is Nothing to Do and Only a Permutation at Home

2 seconds
256 megabytes
Very hard

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:

In one iteration you do the following:

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.

Input

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.

Output

Print the number of seconds that will pass until the process ends, modulo 10^9+7.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Note

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.