# [AGC024E] Sequence Growing Hard

## 题目描述

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