# [GDKOI2024 提高组] 鸡

## 题目描述

对于一个非负整数序列 $a$，定义它对应的独立集序列 $f(a)$：

- 假设将 $a_i$ 改为 $0$，此时选出若干个两两不相邻的数使得它们的和最大，则 $f(a)_i$ 表示和的最大值。

现在给定 $n, m$，求有多少个长度为 $b$ 的非负整数序列 $b$ 满足以下条件：

- 存在至少一个长度为 $n$，值域为 $[0, m]$ 的非负整数序列 $a$ 使得 $f(a) = b$。

答案对给定的质数 $\textit{MOD}$ 取模。

## 输入格式

共一行，三个数，表示 $n, m, \textit{MOD}$。

## 输出格式

共一行，一个数，表示答案。

## 样例 #1

### 样例输入 #1

```
3 1 1000000007
```

### 样例输出 #1

```
6
```

## 样例 #2

### 样例输入 #2

```
4 2 1000000007
```

### 样例输出 #2

```
47
```

## 样例 #3

### 样例输入 #3

```
20 24 1000000007
```

### 样例输出 #3

```
901565358
```

## 样例 #4

### 样例输入 #4

```
123 234 1000000009
```

### 样例输出 #4

```
141754844
```

## 样例 #5

### 样例输入 #5

```
1234 2345 1004535809
```

### 样例输出 #5

```
576196526
```

## 提示

**本题使用子任务捆绑测试。**

对于 $100\%$ 的数据，$1 \leq n, m \leq 3 \times 10^3$，$n \geq 2$，$10^9 < \textit{MOD} < 1.01 \times 10^9$，$\textit{MOD}$ 为质数。

- Subtask 1（10%）：$n, m \leq 5$。
- Subtask 2（15%）：$n \leq 300$，$m = 1$。
- Subtask 3（25%）：$n \leq 300$，$m ≤ 5$。
- Subtask 4（20%）：$n, m \leq 50$。
- Subtask 5（15%）：$n, m \leq 300$。
- Subtask 6（15%）：无特殊限制。