AT_abc378_g.[ABC378G] Everlasting LIDS

给定整数 $A,B,M$。

有 $(1,2,\ldots,AB-1)$ 的一个排列 $P=(P_1,\ldots,P_{AB-1})$，请问满足以下所有条件的排列有多少种？请输出个数对 $M$ 取模的结果。

• $P$ 的最长上升子序列长度为 $A$。
• $P$ 的最长下降子序列长度为 $B$。
• 存在整数 $n$，使得即使在 $P$ 的末尾添加 $n+0.5$，$P$ 的最长上升子序列长度和最长下降子序列长度都不会发生变化。

输入以如下格式从标准输入读入。

$A$ $B$ $M$

请输出满足条件的排列个数对 $M$ 取模的结果。

限制条件

• 输入的所有数都是整数。
• $2\leq A,B$
• $AB\leq 120$
• $10^8\leq M\leq 10^9$
• $M$ 是素数。

样例解释 1

例如，$P=(2,4,5,1,3)$ 满足条件。可以如下验证：

• $P$ 的最长上升子序列长度为 $3$。
• $P$ 的最长下降子序列长度为 $2$。
• 取 $n=4$，则 $(2,4,5,1,3,4.5)$ 的最长上升子序列长度为 $3$，最长下降子序列长度为 $2$。
  满足条件的 $(1,2,3,4,5)$ 的排列共有 $10$ 种。

样例解释 2

请输出个数对 $M$ 取模的结果。

由 ChatGPT 4.1 翻译