[AGC024E] Sequence Growing Hard

给定 $n$, $k$, $m$ , 问有多少个序列组 $(A_0,A_1,…,A_n)$ 满足：序列 $A_i$ 的元素个数为 $i$ ; 所有元素都在 $[1,k]$ 内; $\forall i\in[0,n)$ , $A_i$ 是 $A_{i+1}$ 的子序列且 $A_i$ 的字典序小于 $A_{i+1}$. 输出在 $\bmod m$ 意义下的答案.

[problemUrl]: https://atcoder.jp/contests/agc024/tasks/agc024_e 次の条件を満たす数列の組 $ (A_0,A_1,...,A_N) $ としてありうるものの個数を $ M $ で割ったあまりを求めてください。 - 全ての $ i(0\leq\ i\leq\ N) $ に対し、$ A_i $ は $ 1 $ 以上 $ K $ 以下の整数からなる長さ $ i $ の数列である - 全ての $ i(1\leq\ i\leq\ N) $ に対し、$ A_{i-1} $ は $ A_i $ の部分列である。すなわち、ある $ 1\leq\ x_i\leq\ i $ が存在し、$ A_i $ の $ x_i $ 文字目を取り除いてできる数列が $ A_{i-1} $ に一致する - 全ての $ i(1\leq\ i\leq\ N) $ に対し、$ A_i $ は辞書順で $ A_{i-1} $ より大きい

入力は以下の形式で標準入力から与えられる。 > $ N $ $ K $ $ M $

数列の組 $ (A_0,A_1,...,A_N) $ としてありうるものの個数を $ M $ で割ったあまりを出力せよ。

2 2 100

5

4 3 999999999

358

150 150 998244353

186248260

### 制約 - $ 1\ \leq\ N,K\ \leq\ 300 $ - $ 2\ \leq\ M\ \leq\ 10^9 $ - $ N,K,M $ は整数である ### Sample Explanation 1 以下の $ 5 $ つの組が条件を満たします。 - $ (),(1),(1,1) $ - $ (),(1),(1,2) $ - $ (),(1),(2,1) $ - $ (),(2),(2,1) $ - $ (),(2),(2,2) $