AT_agc065_b [AGC065B] Erase and Insert

[problemUrl]: https://atcoder.jp/contests/agc065/tasks/agc065_b $ (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 $ で割ったあまりを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ P_1 $ $ P_2 $ $ \dots $ $ P_N $

答えを出力せよ。

### 制約 - $ 1\ \le\ N\ \le\ 5000 $ - $ P $ は $ (1,2,\dots,N) $ の順列 ### Sample Explanation 1 例えば、以下のような操作をすると最終的に $ 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 $ 個あります。