AT_agc065_b [AGC065B] Erase and Insert

题目描述

给定一个 $(1,2,\dots,N)$ 的排列 $P$。另外，还有一个排列 $Q=(1,2,\dots,N)$。

对 $Q$ 依次进行如下操作，操作编号为 $i=1,2,\dots,N$：

• 从 $Q$ 中删除 $i$，然后将 $i$ 插入到 $Q$ 的任意一个位置。

经过 $N$ 次操作后，问有多少种操作方法可以使得 $P$ 和 $Q$ 相等。请将答案对 $10^9+7$ 取模后输出。

输入格式

输入通过标准输入给出，格式如下：

$N$ $P_1$ $P_2$ $\dots$ $P_N$

输出格式

请输出答案。

样例 1

输入

3
1 2 3

输出

5

样例 2

输入

4
2 4 1 3

输出

11

样例 3

输入

15
7 5 14 10 4 2 3 6 8 11 12 1 15 13 9

输出

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

输出

33525150

说明/提示

限制

• $1\leq N\leq 5000$
• $P$ 是 $(1,2,\dots,N)$ 的一个排列

样例解释 1

例如，按照如下操作，最终 $Q=(1,2,3)$：

• 从 $Q=(1,2,3)$ 中删除 $1$，将 $1$ 插入到 $2,3$ 之间。此时 $Q=(2,1,3)$。
• 从 $Q=(2,1,3)$ 中删除 $2$，将 $2$ 插入到 $Q$ 的末尾。此时 $Q=(1,3,2)$。
• 从 $Q=(1,3,2)$ 中删除 $3$，将 $3$ 插入到 $Q$ 的末尾。此时 $Q=(1,2,3)$。

包括上述方法在内，使得最终 $Q=(1,2,3)$ 的操作方法共有 $5$ 种。

由 ChatGPT 4.1 翻译