配点 : $1000$ 点

問題文

平面上に $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$ を整列してできた列を連結し，新しい列を作る．
• 整数 $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$ で割った余り求めてください．

制約

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

入力

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

$N$

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

出力

答えを出力せよ．

3
3 1 2

3

以下の $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))$ を得る．
• 集合 $\{(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))$ を得る．

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