题目描述

平面上に $N$ 個の点があり，そのうち $i$ 番目 ($1\ \leq\ i\ \leq\ N$) の点は $(i,P_i)$ です． なお，$(P_1,P_2,\cdots,P_N)$ は $(1,2,\cdots,N)$ の順列になっています．

あなたは，空でない点の集合 $s$ に対し，整列という操作を行えます． 整列とは，以下のような再帰的な操作です．

• $s$ に含まれる点がちょうど $1$ 個のとき，その点だけからなる列を作る．
• $s$ に含まれる点が $2$ 個以上のとき，以下の $2$ 種類のうちどちらかの操作を行い，$s$ に含まれる点からなる列を作る．
  • 整数 $x$ を自由に選び，$X$座標が $x$ 未満の点の集合（この集合を $a$ と呼ぶ）と，それ以外の点の集合（この集合を $b$ と呼ぶ）に分ける． ここで，$a$ や $b$ が空であってはならない． $a$ を整列してできた列の後ろに，$b$ を整列してできた列を連結し，新しい列を作る．
  • 整数 $y$ を自由に選び，$Y$座標が $y$ 未満の点の集合（この集合を $a$ と呼ぶ）と，それ以外の点の集合（この集合を $b$ と呼ぶ）に分ける． ここで，$a$ や $b$ が空であってはならない． $a$ を整列してできた列の後ろに，$b$ を整列してできた列を連結し，新しい列を作る．

点の集合 $\{(1,P_1),(2,P_2),\cdots,(N,P_N)\}$ に対して整列を行うとき，その結果としてありうる列の個数を $10^9+7$ で割った余り求めてください．

输入格式

入力は以下の形式で標準入力から与えられる．

$N$ $P_1$ $P_2$ $\cdots$ $P_N$

输出格式

答えを出力せよ．

题目大意

有一个长为 $n$ 的点列 $\{(i,p_i)\}$，每次可以选择 $x/y$ 和某个坐标将点列分成左右/上下两边（保持两边相对顺序不边），然后分别递归下去，直到区间长度为 1。求可以得到多少本质不同的点列。$n\leq 30$

3
3 1 2

3

5
1 2 3 4 5

1

10
3 6 4 8 7 2 10 5 9 1

1332

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

641915679

提示

制約

• $1\ \leq\ N\ \leq\ 30$
• $(P_1,P_2,\cdots,P_N)$ は $(1,2,\cdots,N)$ の順列
• 入力される値はすべて整数である

Sample Explanation 1

以下の $3$ 種類の列を得ることができます． - $((1,3),(2,1),(3,2))$ - $((2,1),(3,2),(1,3))$ - $((2,1),(1,3),(3,2))$ たとえば，$((2,1),(1,3),(3,2))$ という列は，以下の手順で得られます． - 集合 $\{(1,3),(2,1),(3,2)\}$ に対して整列を行う．$Y$座標が $2$ 未満の点の集合 ($=\{(2,1)\}$) とそれ以外の点の集合 ($=\{(1,3),(3,2)\}$) に分ける． - 集合 $\{(2,1)\}$ に対して整列を行う．列 $((2,1))$ を得る． - 集合 $\{(1,3),(3,2)\}$ に対して整列を行う．$X$座標が $3$ 未満の点の集合とそれ以外の点の集合に分ける． - $\{(1,3)\}$ に対して整列を行う．列 $((1,3))$ を得る． - $\{(3,2)\}$ に対して整列を行う．列 $((3,2))$ を得る． - 得られた $2$ つの列を連結し，列 $((1,3),(3,2))$ を得る． - 得られた $2$ つの列を連結し，列 $((2,1),(1,3),(3,2))$ を得る．