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\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 翻译