Superpermutations

Once, during his informatics class, Dima solved all the problems about permutations. Then he came up with a problem about a superpermutation.

A superpermutation of order $n$ is a sequence of integers from $1$ to $n$ such that every permutation of the numbers from $1$ to $n$ occurs as a contiguous subsegment of the sequence.

Dima came up with the following algorithm for generating superpermutations:

• $s_1 = [1]$.
• Set $s_{n+1}$ equal to $s_n$ at first.
• Consider all subsegments of $s_n$ of length $n$, from left to right, in order of increasing start position.
• If the current subsegment $s_n[l], s_n[l+1], \ldots, s_n[l+n-1]$ is a permutation of the numbers from $1$ to $n$ (each number from $1$ to $n$ occurs exactly once), insert the numbers $n+1, s_n[l], s_n[l+1], \ldots, s_n[l+n-1]$ into $s_{n+1}$ right after the last element $s_n[l+n-1]$ of that subsegment.

Here is how the superpermutations of order $1$, $2$, $3$ and $4$ are built.

By definition, $s_1 = [1]$.

Set $s_2 = [1]$. The only subsegment of length $1$ is $[1]$, which is a permutation, so we insert $[2, 1]$ after it. The result is $s_2 = [1, 2, 1]$.

Set $s_3 = [1, 2, 1]$. The subsegment $[1, 2]$ is a permutation, so we insert $[3, 1, 2]$ after it, giving $[1, 2, 3, 1, 2, 1]$. The subsegment $[2, 1]$ is also a permutation, so we insert $[3, 2, 1]$ after it. The result is $s_3 = [1, 2, 3, 1, 2, 1, 3, 2, 1]$.

Set $s_4 = [1, 2, 3, 1, 2, 1, 3, 2, 1]$. The subsegments of length $3$ that are permutations are, in order, $[1, 2, 3]$, $[2, 3, 1]$, $[3, 1, 2]$ and $[2, 1, 3]$. We insert $[4, 1, 2, 3]$, $[4, 2, 3, 1]$, $[4, 3, 1, 2]$ and $[4, 2, 1, 3]$ after them, respectively. The subsegments $[1, 2, 1]$ is not a permutation, so nothing happens there. The remaining two permutations, $[1, 3, 2]$ and $[3, 2, 1]$, are handled the same way.

Dima noticed that this method builds a superpermutation in which every permutation occurs exactly once. To check his work, he wants to find the position where a given permutation $a_1, \dots, a_n$ occurs in his superpermutation $s_n$. Positions start at 1.

Since $s_n$ is extremely long, output the index of the first element of $s_n$ where the occurrence starts, modulo $10^9 + 7$.

The first line contains a single integer $n$, the length of the permutation ($1 \le n \le 300\,000$).

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$, the given permutation ($1 \le a_i \le n$, all $a_i$ are distinct).

Output a single integer, the position where the permutation $a_1, a_2, \ldots, a_n$ occurs in the superpermutation of order $n$, modulo $10^9+7$.