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)\}$.

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.

Input

Input is given from Standard Input in the following format:

N
P_1 P_2 \cdots P_N

Output

Print the answer.