Problem Statement

There are N points in a plane, the $i-th (1 \leq i \leq N)$ of which is (i,P_i).
Here, $(P_1,P_2,\cdots,P_N)$ is a permutation of $(1,2,\cdots,N)$.
You can arrange a non-empty set s of points, which is a recursive operation defined as follows.

• If s contains exactly one point, arranging it creates a sequence composed of just that point.
• If s contains two or more points, arranging it creates a sequence composed of those points by doing one of the following two operations.
• Choose any integer x and divide s into two: the set a of points whose X-coordinates are less than x and the set b of the other points.
  Here, neither a nor b should be empty.
  Create a sequence by concatenating the sequence obtained by arranging a and the sequence obtained by arranging b in this order.
• Choose any integer y and divide s into two: the set a of points whose Y-coordinates are less than y and the set b of the other points.
  Here, neither a nor b should be empty.
  Create a sequence by concatenating the sequence obtained by arranging a and the sequence obtained by arranging b in this order.

Find the number, modulo (10^9+7), of sequences that can be obtained by arranging the set of points ${(1,P_1),(2,P_2),\cdots,(N,P_N)$}.

Input

Input is given from Standard Input in the following format:
N
$P_1 P_2 \cdots P_N$

Output

Print the answer.

Constraints

• $1 \leq N \leq 30$
• $(P_1,P_2,\cdots,P_N)$ is a permutation of $(1,2,\cdots,N)$.
• All values in input are integers.

Sample Input 1

3
3 1 2

Sample Output 1

3

The following three sequences can be obtained.

• ((1,3),(2,1),(3,2))
• ((2,1),(3,2),(1,3))
• ((2,1),(1,3),(3,2))

For example, the sequence ((2,1),(1,3),(3,2)) can be obtained as follows.

• Arrange the set {(1,3),(2,1),(3,2)} by dividing it to the set of points whose Y-coordinates are less than 2 (={(2,1)}) and the set of the other points (={(1,3),(3,2)}).
• Arrange the set {(2,1)} to obtain the sequence ((2,1)).
• Arrange the set {(1,3),(3,2)} by dividing it to the set of points whose X-coordinates are less than 3 and the set of the other points.
• Arrange the set {(1,3)} to obtain the sequence ((1,3)).
• Arrange the set {(3,2)} to obtain the sequence ((3,2)).

• Concatenate the resulting two sequences to obtain the sequence ((1,3),(3,2)).

• Concatenate the resulting two sequences to obtain the sequence ((2,1),(1,3),(3,2)).

Sample Input 2

5
1 2 3 4 5

Sample Output 2

1

Sample Input 3

10
3 6 4 8 7 2 10 5 9 1

Sample Output 3

1332

Sample Input 4

30
7 11 8 26 4 13 28 5 14 1 16 27 10 2 23 25 17 6 3 18 24 15 9 22 21 29 12 20 19 30

Sample Output 4

641915679

见题面 Input 部分

见题面 Output 部分