103786: [Atcoder]ABC378 G - Everlasting LIDS

Problem Statement

You are given integers $A$, $B$, and $M$.

How many permutations $P = (P_1, \dots, P_{AB-1})$ of $(1, 2, \ldots, AB - 1)$ satisfy all of the following conditions? Find the count modulo $M$.

• The length of a longest increasing subsequence of $P$ is $A$.
• The length of a longest decreasing subsequence of $P$ is $B$.
• There exists an integer $n$ such that appending $n + 0.5$ to the end of $P$ does not change either of the lengths of a longest increasing subsequence and a longest decreasing subsequence.

Constraints

• All input values are integers.
• $2 \leq A, B$
• $AB \leq 120$
• $10^8 \leq M \leq 10^9$
• $M$ is a prime.

Input

The input is given from Standard Input in the following format:

$A$ $B$ $M$

Output

Print the number of permutations satisfying the conditions, modulo $M$.

Sample Input 1

3 2 998244353

Sample Output 1

10

For example, $P = (2, 4, 5, 1, 3)$ satisfies the conditions. This can be confirmed as follows:

• The length of a longest increasing subsequence of $P$ is $3$.
• The length of a longest decreasing subsequence of $P$ is $2$.
• For $n = 4$, the lengths of longest increasing and decreasing subsequences of $(2, 4, 5, 1, 3, 4.5)$ are $3$ and $2$, respectively.

There are $10$ permutations of $(1, 2, 3, 4, 5)$ that satisfy the conditions.

Sample Input 2

10 12 924844033

Sample Output 2

623378361

Print the count modulo $M$.

问题陈述

给定整数 $A$，$B$ 和 $M$。

有多少排列 $P = (P_1, \dots, P_{AB-1})$ 满足以下所有条件？请找到模 $M$ 后的计数。

• $P$ 的最长递增子序列的长度是 $A$。
• $P$ 的最长递减子序列的长度是 $B$。
• 存在一个整数 $n$，将 $n + 0.5$ 追加到 $P$ 的末尾不会改变最长递增子序列和最长递减子序列的长度。

约束条件

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

输入

输入从标准输入以下格式给出：

$A$ $B$ $M$

输出

打印满足条件的排列数，模 $M$。

样本输入 1

3 2 998244353

样本输出 1

10

例如，$P = (2, 4, 5, 1, 3)$ 满足条件。这可以按以下方式确认：

• $P$ 的最长递增子序列的长度是 $3$。
• $P$ 的最长递减子序列的长度是 $2$。
• 对于 $n = 4$，$(2, 4, 5, 1, 3, 4.5)$ 的最长递增和递减子序列的长度分别是 $3$ 和 $2$。

有 $10$ 个 $(1, 2, 3, 4, 5)$ 的排列满足条件。

样本输入 2

10 12 924844033

样本输出 2

623378361

打印模 $M$ 后的计数。