AT_dp_t Permutation

[problemUrl]: https://atcoder.jp/contests/dp/tasks/dp_t $ N $ を正整数とします。 長さ $ N\ -\ 1 $ の文字列 $ s $ が与えられます。 $ s $ は `` からなります。 $ (1,\ 2,\ \ldots,\ N) $ を並べ替えた順列 $ (p_1,\ p_2,\ \ldots,\ p_N) $ であって、次の条件を満たすものは何通りでしょうか？ $ 10^9\ +\ 7 $ で割った余りを求めてください。 - 各 $ i $ ($ 1\ \leq\ i\ \leq\ N\ -\ 1 $) について、$ s $ の $ i $ 文字目が `\ p_{i\ +\ 1} $ である。

N/A

N/A

### 制約 - $ N $ は整数である。 - $ 2\ \leq\ N\ \leq\ 3000 $ - $ s $ は長さ $ N\ -\ 1 $ の文字列である。 - $ s $ は `` からなる。 ### Sample Explanation 1 条件を満たす順列は次の $ 5 $ 通りです。 - $ (1,\ 3,\ 2,\ 4) $ - $ (1,\ 4,\ 2,\ 3) $ - $ (2,\ 3,\ 1,\ 4) $ - $ (2,\ 4,\ 1,\ 3) $ - $ (3,\ 4,\ 1,\ 2) $ ### Sample Explanation 2 条件を満たす順列は次の $ 1 $ 通りです。 - $ (1,\ 2,\ 3,\ 4,\ 5) $ ### Sample Explanation 3 答えを $ 10^9\ +\ 7 $ で割った余りを出力することを忘れずに。