题目描述

次の条件を満たす数列の組 $(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$ で割ったあまりを出力せよ。

题目大意

给定 $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$ 意义下的答案.

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