AT_agc024_e.[AGC024E] Sequence Growing Hard

请计算满足以下条件的数列组 $(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 \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 翻译