selfpermutation

Description

There exists a sequence A of size N whose each element is an integer from 1 to N. There is no integer that appears more than once in the sequence A.

Pak Dengklek wants to play with this sequence. He can perform deletion operation by doing the following:

1. Choose two adjacent integers in sequence A.
2. From both of the chosen integers, delete the larger integer.

For example, if the sequence is [2, 5, 1, 3, 4], and Pak Dengklek chooses 1 and 3 which are adjacent in that sequence, then Pak Dengklek can delete 3 and the sequence turns into [2, 5, 1, 4].

Pak Dengklek can perform deletion operations any number of times (possibly none) as long as the sequence has at least two integers. Pak Dengklek wonders how many different final sequences he can obtain after performing the deletion operations. Since the number of different final sequences can be very large, calculate the value modulo 1000000007.

Constraints

• 1 ≤ N ≤ 300000
• 1 ≤ A_i ≤ N
• There is no integer that appears more than once in A.

Subtasks

1. (8 points) Contains only the following test case:
   N = 6, A = [2, 5, 1, 3, 4, 6].
2. (20 points) N ≤ 200
3. (13 points) N ≤ 2000, A_i = i
4. (9 points) A_i = i
5. (23 points) N ≤ 2000
6. (27 points) No additional constraints.

Input

The input is given with the following format:

N
A1 A2 … AN

Output

An integer representing the number of different sequences that can be obtained modulo 1\;000\;000\;007.

Sample Input 1

3
2 3 1

Sample Output 1

3

Explanation of Sample 1

The following are possible deletion operations that can be performed on the sequence:

• [2, 3, 1] without any deletion.
• [2, 3, 1] → [2, 1] by choosing 2 and 3. Choosing 3 and 1 will also result in the same sequence.
• [2, 3, 1] → [2, 1] → [1]

Sample Input 2

4
2 1 4 3

Sample Output 2

6

Explanation of Sample 2

The following are possible deletion operations that can be performed on the sequence:

• [2, 1, 4, 3]
• [2, 1, 4, 3] → [1, 4, 3]
• [2, 1, 4, 3] → [1, 4, 3] → [1, 3]
• [2, 1, 4, 3] → [1, 4, 3] → [1, 3] → [1]
• [2, 1, 4, 3] → [2, 1, 3]
• [2, 1, 4, 3] → [2, 1, 3] → [2, 1]