题目描述

请计算满足以下条件的数列组 $(A_0, A_1, \ldots, 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$。

$N$ $K$ $M$

输出格式

输出满足条件的数列组 $(A_0, A_1, \ldots, A_N)$ 的个数对 $M$ 取模的结果。

样例 1

输入

2 2 100

输出

5

样例 2

输入

4 3 999999999

输出

358

样例 3

输入

150 150 998244353

输出

186248260

说明/提示

限制

• $1 \leq N, K \leq 300$
• $2 \leq M \leq 10^9$
• $N, K, M$ 均为整数

样例解释 1

以下 $5$ 组数列满足条件：

• $(), (1), (1,1)$
• $(), (1), (1,2)$
• $(), (1), (2,1)$
• $(), (2), (2,1)$
• $(), (2), (2,2)$

由 ChatGPT 4.1 翻译