[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://agc024.contest.atcoder.jp/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} $ より大きい Find the number of the possible tuples of sequences $ (A_0,A_1,...,A_N) $ that satisfy all of the following conditions, modulo $ M $ : - For every $ i $ $ (0\leq\ i\leq\ N) $ , $ A_i $ is a sequence of length $ i $ consisting of integers between $ 1 $ and $ K $ (inclusive); - For every $ i $ $ (1\leq\ i\leq\ N) $ , $ A_{i-1} $ is a subsequence of $ A_i $ , that is, there exists $ 1\leq\ x_i\leq\ i $ such that the removal of the $ x_i $ -th element of $ A_i $ would result in a sequence equal to $ A_{i-1} $ ; - For every $ i $ $ (1\leq\ i\leq\ N) $ , $ A_i $ is lexicographically larger than $ A_{i-1} $ .

输入输出格式

输入格式


Input is given from Standard Input in the following format: ``` $ N $ $ K $ $ M $ ```

输出格式


Print the number of the possible tuples of sequences $ (A_0,A_1,...,A_N) $ , modulo $ M $ .

输入输出样例

输入样例 #1

2 2 100

输出样例 #1

5

输入样例 #2

4 3 999999999

输出样例 #2

358

输入样例 #3

150 150 998244353

输出样例 #3

186248260

输入样例 #4

2 2 100

输出样例 #4

5

输入样例 #5

4 3 999999999

输出样例 #5

358

输入样例 #6

150 150 998244353

输出样例 #6

186248260

说明

### 制約 - $ 1\ \leq\ N,K\ \leq\ 300 $ - $ 2\ \leq\ M\ \leq\ 10^9 $ - $ N,K,M $ は整数である ### Constraints - $ 1\ \leq\ N,K\ \leq\ 300 $ - $ 2\ \leq\ M\ \leq\ 10^9 $ - $ N $ , $ K $ and $ M $ are integers. ### Sample Explanation 1 以下の $ 5 $ つの組が条件を満たします。 - $ (),(1),(1,1) $ - $ (),(1),(1,2) $ - $ (),(1),(2,1) $ - $ (),(2),(2,1) $ - $ (),(2),(2,2) $ ### Sample Explanation 4 Five tuples below satisfy the conditions: - $ (),(1),(1,1) $ - $ (),(1),(1,2) $ - $ (),(1),(2,1) $ - $ (),(2),(2,1) $ - $ (),(2),(2,2) $