슈퍼순열

디마는 정보 수업 시간에 순열과 관련된 문제를 모두 풀었다. 그 뒤 그는 슈퍼순열에 관한 문제를 떠올렸다.

차수가 $n$인 슈퍼순열은 1부터 $n$까지의 정수로 이루어진 수열이며, 1부터 $n$까지의 수로 만들 수 있는 모든 순열이 이 수열의 연속된 부분 구간으로 나타난다.

디마는 다음과 같은 슈퍼순열 생성 알고리즘을 고안했다.

• $s_1 = [1]$이다.
• 먼저 $s_{n+1}$을 $s_n$과 같게 둔다.
• $s_n$의 길이 $n$인 부분 구간을 시작 위치가 작은 순서대로 왼쪽부터 차례로 본다.
• 현재 부분 구간 $s_n[l], s_n[l+1], \ldots, s_n[l+n-1]$이 1부터 $n$까지의 수의 순열이면(각 수가 정확히 한 번씩 나타나면), 그 부분 구간의 마지막 원소 $s_n[l+n-1]$ 바로 뒤에 $n+1, s_n[l], s_n[l+1], \ldots, s_n[l+n-1]$을 삽입한다.

차수 1, 2, 3, 4의 슈퍼순열이 만들어지는 과정은 다음과 같다.

정의에 따라 $s_1 = [1]$이다.

$s_2$는 $[1]$로 둔다. 길이 1인 부분 구간은 $[1]$뿐이며 이는 순열이므로, 그 뒤에 $[2, 1]$을 삽입한다. 결과는 $s_2 = [1, 2, 1]$이다.

$s_3$는 $[1, 2, 1]$로 둔다. 부분 구간 $[1, 2]$는 순열이므로 그 뒤에 $[3, 1, 2]$를 삽입해 $[1, 2, 3, 1, 2, 1]$을 얻는다. 부분 구간 $[2, 1]$도 순열이므로 그 뒤에 $[3, 2, 1]$을 삽입한다. 결과는 $s_3 = [1, 2, 3, 1, 2, 1, 3, 2, 1]$이다.

$s_4$는 $[1, 2, 3, 1, 2, 1, 3, 2, 1]$로 둔다. 길이 3인 부분 구간 중 순열인 것은 차례로 $[1, 2, 3]$, $[2, 3, 1]$, $[3, 1, 2]$, $[2, 1, 3]$이며, 각각의 뒤에 $[4, 1, 2, 3]$, $[4, 2, 3, 1]$, $[4, 3, 1, 2]$, $[4, 2, 1, 3]$을 삽입한다. $[1, 2, 1]$은 순열이 아니므로 아무 일도 일어나지 않는다. 남은 두 순열 $[1, 3, 2]$와 $[3, 2, 1]$도 같은 방식으로 처리한다.

디마는 이 방법으로 만든 슈퍼순열에서 모든 순열이 정확히 한 번씩 나타난다는 점을 발견했다. 자신의 작업에 실수가 없는지 확인하려고, 주어진 순열 $a_1, \dots, a_n$이 슈퍼순열 $s_n$에서 나타나는 위치를 구하려 한다. 위치는 1부터 센다.

$s_n$의 길이가 매우 크므로, 이 순열이 시작하는 $s_n$의 첫 원소의 번호를 $10^9 + 7$로 나눈 나머지로 구하라.

첫 줄에 순열의 길이 $n$이 주어진다 ($1 \le n \le 300\,000$).

둘째 줄에는 주어진 순열 $a_1, a_2, \ldots, a_n$이 $n$개의 정수로 주어진다 ($1 \le a_i \le n$, 모든 $a_i$는 서로 다르다).

차수 $n$의 슈퍼순열에서 순열 $a_1, a_2, \ldots, a_n$이 나타나는 위치를 $10^9+7$로 나눈 나머지로 한 줄에 출력한다.