AT_agc055_c [AGC055C] Weird LIS

[problemUrl]: https://atcoder.jp/contests/agc055/tasks/agc055_c 整数 $ N,\ M $ が与えられます。次の条件を満たす長さ $ N $ の列 $ A=[A_1,\ A_2,\ \ldots,\ A_N] $ の個数を求めてください。 - $ 2\ \le\ A_i\ \le\ M $ ($ 1\ \leq\ i\ \leq\ N $) - $ 1 $ から $ N $ までの整数の順列 $ P=[P_1,P_2,\ldots,P_N] $ であって次の性質を持つものが存在する。 - $ 1 $ から $ N $ までの各 $ i $ について、$ A_i $ は列 $ [P_1,\ P_2,\ \ldots,\ P_{i-1},\ P_{i+1},\ \ldots,\ P_{N-1},\ P_N] $ の最長増加部分列の長さに等しい。 この個数は非常に大きい可能性があるため、これを素数 $ Q $ で割った余りを出力してください。

N/A

N/A

### 制約 - $ 3\ \le\ N\ \le\ 5000 $ - $ 2\ \le\ M\ \le\ N-1 $ - $ 10^8\ \le\ Q\ \le\ 10^9 $ - $ Q $ は素数である。 ### Sample Explanation 1 このような列は $ [2,\ 2,\ 2] $ のみです。ここで $ [1,\ 2,\ 3] $ という順列が存在して性質を満たします。 ### Sample Explanation 2 このような列は次の $ 9 $ 個です: $ [2,\ 2,\ 2,\ 2] $, $ [2,\ 2,\ 2,\ 3] $, $ [2,\ 2,\ 3,\ 2] $, $ [2,\ 2,\ 3,\ 3] $, $ [2,\ 3,\ 2,\ 2] $, $ [2,\ 3,\ 3,\ 2] $, $ [3,\ 2,\ 2,\ 2] $, $ [3,\ 3,\ 2,\ 2] $, $ [3,\ 3,\ 3,\ 3] $。 ### Sample Explanation 3 このような列は $ [2,\ 2,\ 2,\ 2,\ 2] $ のみです。