問題文

平面上に $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$ で割った余り求めてください．

制約

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

入力

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

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

出力

答えを出力せよ．

入力例 1

3
3 1 2

出力例 1

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

5
1 2 3 4 5

出力例 2

1

入力例 3

10
3 6 4 8 7 2 10 5 9 1

出力例 3

1332

入力例 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

出力例 4

641915679