AT_1_stpc2025_1_c.Sum of Three Inversions

给定整数 $N, X, Y, K, M$。请你求满足以下所有条件的三元组 $(A, B, C)$ 的个数，输出其对 $M$ 取模的结果。其中三元组由长度为 $N$ 的整数列 $A, B, C$ 组成，记数列 $a$ 的第 $k$ 个元素为 $a_k$。

• 对于 $i = 1, 2, \dots, N$，$(A_i, B_i, C_i)$ 是 $(1, 2, 3)$ 的一个排列。
• $A$ 中包含 $X$ 个 $1$ 和 $Y$ 个 $2$。
• $A$ 的逆序对数、$B$ 的逆序对数和 $C$ 的逆序对数之和为 $K$。

逆序对数的定义如下：对于数列 $a$，逆序对数是满足 $1 \leq i < j \leq |a|$ 且 $a_i > a_j$ 的整数对 $(i, j)$ 的个数。

输入为以下格式：

$N\ X\ Y\ K\ M$

请输出答案。

样例解释 1

满足条件的 $(A, B, C)$ 共存在 $24$ 种。例如，当 $A = (1, 2, 3),\ B = (3, 3, 2),\ C = (2, 1, 1)$ 时，$(A, B, C)$ 满足所有条件。

样例解释 2

不存在满足条件的 $(A, B, C)$。

数据范围

• 输入均为整数
• $2 \leq N \leq 50$
• $0 \leq X, Y \leq N$
• $X + Y \leq N$
• $0 \leq K \leq \frac{3}{2} N (N - 1)$
• $10^8 \leq M \leq 10^9$

由 ChatGPT 5 翻译