← 返回题目列表

AtCoder · agc065_b

B. 擦除和插入

中文机器翻译题面 查看原题

分数: 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