CF1439D INOI Final Contests

今天是 INOI（伊朗信息学奥林匹克竞赛）决赛。比赛教室是一排共有 $n$ 台电脑的房间。所有电脑从左到右依次编号为 $1$ 到 $n$。有 $m$ 位参赛者，编号为 $1$ 到 $m$。 我们有一个长度为 $m$ 的数组 $a$，其中 $a_i$（$1 \leq a_i \leq n$）表示第 $i$ 位参赛者想要坐在第 $a_i$ 号电脑后面。 另外，还有一个长度为 $m$ 的数组 $b$，由字符 'L' 和 'R' 组成。$b_i$ 表示第 $i$ 位参赛者进入房间的方向。'L' 表示该参赛者从第 $1$ 号电脑的左侧进入房间，并从左向右行进；'R' 表示该参赛者从第 $n$ 号电脑的右侧进入房间，并从右向左行进。 参赛者按照 $1$ 到 $m$ 的顺序依次进入房间。第 $i$ 位参赛者按照 $b_i$ 的方向进入，并试图坐在第 $a_i$ 号电脑后面。如果该电脑已被占用，他会沿着自己的方向继续前进，直到找到第一个空闲的电脑，然后坐下。如果他没有找到任何空闲的电脑，他会感到沮丧并放弃比赛。 第 $i$ 位参赛者的“疯狂值”定义为他分配到的电脑（$a_i$）与他实际坐下的电脑之间的距离。电脑 $i$ 和 $j$ 之间的距离为 $|i-j|$。 数组 $a$ 中的值可以相同。总共有 $n^m \cdot 2^m$ 种可能的数组对 $(a, b)$。 请考虑所有不会有参赛者放弃比赛的数组对 $(a, b)$。对于每一种情况，计算所有参赛者的疯狂值之和。请你求出所有这些情况的疯狂值总和。 你将得到一个质数模数 $p$。请输出答案对 $p$ 取模的结果。

一行包含三个整数 $n$、$m$、$p$（$1 \leq m \leq n \leq 500, 10^8 \leq p \leq 10^9 + 9$）。 保证 $p$ 是质数。

仅输出一个整数，表示所求的总和对 $p$ 取模的结果。

在第一个测试样例中，有三种可能的数组 $a$：$\{1\}$、$\{2\}$ 和 $\{3\}$，以及两种可能的数组 $b$：$\{\mathtt{L}\}$ 和 $\{\mathtt{R}\}$。对于所有六种 $(a, b)$ 组合，唯一的参赛者都会坐在 $a_1$ 号电脑后面，因此他的疯狂值都是 $0$。所以总的疯狂值之和为 $0$。 在第二个测试样例中，所有不会有参赛者放弃比赛的 $(a, b)$ 组合如下： - $(\{1, 1\}, \{\mathtt{L}, \mathtt{L}\})$，疯狂值之和为 $1$； - $(\{1, 1\}, \{\mathtt{R}, \mathtt{L}\})$，疯狂值之和为 $1$； - $(\{2, 2\}, \{\mathtt{R}, \mathtt{R}\})$，疯狂值之和为 $1$； - $(\{2, 2\}, \{\mathtt{L}, \mathtt{R}\})$，疯狂值之和为 $1$； - 所有 $a \in \{\{1, 2\}, \{2, 1\}\}$ 和 $b \in \{\{\mathtt{L}, \mathtt{L}\}, \{\mathtt{R}, \mathtt{L}\}, \{\mathtt{L}, \mathtt{R}\}, \{\mathtt{R}, \mathtt{R}\}\}$ 的组合，疯狂值之和为 $0$。 所以答案为 $1 + 1 + 1 + 1 + 0 \ldots = 4$。 由 ChatGPT 4.1 翻译