AT_arc138_f [ARC138F] KD Tree

[problemUrl]: https://atcoder.jp/contests/arc138/tasks/arc138_f 平面上に $ 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 $

答えを出力せよ．

### 制約 - $ 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)) $ を得る．