/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 700 点
問題文
(1,2,\dots,N) の順列 P が与えられます。また、(1,2,\dots,N) の順列 Q=(1,2,\dots,N) があります。
Q に以下の操作を i=1,2,\dots,N の順で行います。
- Q から i を削除し、Q に i を 1 個自由な場所に挿入する。
N 個の操作が終わった後に P,Q が等しくなるような操作方法の個数を 10^9+7 で割ったあまりを求めてください。
制約
- 1 \le N \le 5000
- P は (1,2,\dots,N) の順列
入力
入力は以下の形式で標準入力から与えられる。
N P_1 P_2 \dots P_N
出力
答えを出力せよ。
入力例 1
3 1 2 3
出力例 1
5
例えば、以下のような操作をすると最終的に Q = (1,2,3) となります。
- Q=(1,2,3) から 1 を削除し、2,3 の間に 1 を挿入する。Q=(2,1,3) となる。
- Q=(2,1,3) から 2 を削除し、Q の末尾に 2 を挿入する。Q=(1,3,2) となる。
- Q=(1,3,2) から 3 を削除し、Q の末尾に 3 を挿入する。Q=(1,2,3) となる。
この例を合わせて、最終的に Q=(1,2,3) となる操作方法は 5 個あります。
入力例 2
4 2 4 1 3
出力例 2
11
入力例 3
15 7 5 14 10 4 2 3 6 8 11 12 1 15 13 9
出力例 3
306264
入力例 4
30 15 19 13 11 22 27 21 25 1 12 30 28 16 26 10 14 20 2 5 7 23 4 17 6 29 3 18 9 8 24
出力例 4
33525150
Score : 700 points
Problem Statement
You are given a permutation P of (1,2,\dots,N). There is also a permutation Q=(1,2,\dots,N) of (1,2,\dots,N).
Perform the following operation on Q for i=1,2,\dots,N in this order.
- Remove i from Q and insert i into any one position in Q.
Find the number, modulo (10^9+7), of ways to perform N operations such that P and Q are equal after all operations.
Constraints
- 1 \le N \le 5000
- P is a permutation of (1,2,\dots,N).
Input
The input is given from Standard Input in the following format:
N P_1 P_2 \dots P_N
Output
Print the answer.
Sample Input 1
3 1 2 3
Sample Output 1
5
For example, the following operations result in Q = (1,2,3).
- Remove 1 from Q=(1,2,3) and insert it between 2 and 3, making Q = (2,1,3).
- Remove 2 from Q=(2,1,3) and insert it at the end of Q, making Q = (1,3,2).
- Remove 3 from Q=(1,3,2) and insert it at the end of Q, making Q = (1,2,3).
Including this example, five ways to perform operations result in Q=(1,2,3).
Sample Input 2
4 2 4 1 3
Sample Output 2
11
Sample Input 3
15 7 5 14 10 4 2 3 6 8 11 12 1 15 13 9
Sample Output 3
306264
Sample Input 4
30 15 19 13 11 22 27 21 25 1 12 30 28 16 26 10 14 20 2 5 7 23 4 17 6 29 3 18 9 8 24
Sample Output 4
33525150