分数: 700 点
问题陈述
给你一个排列 P of (1,2,\dots,N)。还有一个排列 Q=(1,2,\dots,N) of (1,2,\dots,N).
执行以下操作 Q 为 i=1,2,\dots,N 按此顺序。
- 删除 i 来自 Q 并插入 i 进入任意一个位置 Q.
求模数 (10^9+7),执行方法 N 操作使得 所有操作后 P 和 Q 相等。
约束
- 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).
- 删除 1 来自 Q=(1,2,3) 并将其插入 2 和 3,制作 Q = (2,1,3).
- 删除 2 来自 Q=(2,1,3) 并将其插入到末尾 Q,制作 Q = (1,3,2).
- 删除 3 来自 Q=(1,3,2) 并将其插入到末尾 Q,制作 Q = (1,2,3).
包括此示例,执行操作的五种方法会导致 Q=(1,2,3).
示例输入 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