[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 $ で割ったあまりを出力せよ。

输入输出样例

输入样例 #1

2 2 100

输出样例 #1

5

输入样例 #2

4 3 999999999

输出样例 #2

358

输入样例 #3

150 150 998244353

输出样例 #3

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) $