/ 
Time Limit: 4 sec / Memory Limit: 1024 MB
配点 : 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 を整列してできた列を連結し，新しい列を作る．
点の集合 \{(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
Score : 1000 points
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.
Sample Input 1
3 3 1 2
Sample Output 1
3
The following three sequences can be obtained.
- ((1,3),(2,1),(3,2))
- ((2,1),(3,2),(1,3))
- ((2,1),(1,3),(3,2))
For example, the sequence ((2,1),(1,3),(3,2)) can be obtained as follows.
- Arrange the set \{(1,3),(2,1),(3,2)\} by dividing it to the set of points whose Y-coordinates are less than 2 (=\{(2,1)\}) and the set of the other points (=\{(1,3),(3,2)\}).
- Arrange the set \{(2,1)\} to obtain the sequence ((2,1)).
- Arrange the set \{(1,3),(3,2)\} by dividing it to the set of points whose X-coordinates are less than 3 and the set of the other points.
- Arrange the set \{(1,3)\} to obtain the sequence ((1,3)).
- Arrange the set \{(3,2)\} to obtain the sequence ((3,2)).
- Concatenate the resulting two sequences to obtain the sequence ((1,3),(3,2)).
- Concatenate the resulting two sequences to obtain the sequence ((2,1),(1,3),(3,2)).
Sample Input 2
5 1 2 3 4 5
Sample Output 2
1
Sample Input 3
10 3 6 4 8 7 2 10 5 9 1
Sample Output 3
1332
Sample Input 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
Sample Output 4
641915679