CF1439D.INOI Final Contests

Today is the final contest of INOI (Iranian National Olympiad in Informatics). The contest room is a row with $n$ computers. All computers are numbered with integers from $1$ to $n$ from left to right. There are $m$ participants, numbered with integers from $1$ to $m$.

We have an array $a$ of length $m$ where $a_{i}$ ($1 \leq a_i \leq n$) is the computer behind which the $i$-th participant wants to sit.

Also, we have another array $b$ of length $m$ consisting of characters 'L' and 'R'. $b_i$ is the side from which the $i$-th participant enters the room. 'L' means the participant enters from the left of computer $1$ and goes from left to right, and 'R' means the participant enters from the right of computer $n$ and goes from right to left.

The participants in the order from $1$ to $m$ enter the room one by one. The $i$-th of them enters the contest room in the direction $b_i$ and goes to sit behind the $a_i$-th computer. If it is occupied he keeps walking in his direction until he reaches the first unoccupied computer. After that, he sits behind it. If he doesn't find any computer he gets upset and gives up on the contest.

The madness of the $i$-th participant is the distance between his assigned computer ($a_i$) and the computer he ends up sitting behind. The distance between computers $i$ and $j$ is equal to $|i - j|$.

The values in the array $a$ can be equal. There exist $n^m \cdot 2^m$ possible pairs of arrays $(a, b)$.

Consider all pairs of arrays $(a, b)$ such that no person becomes upset. For each of them let's calculate the sum of participants madnesses. Find the sum of all these values.

You will be given some prime modulo $p$. Find this sum by modulo $p$.

今天是伊朗信息学国家奥林匹克竞赛（INOI）的决赛。比赛场地是一排共 $n$ 台计算机，从左到右依次编号为 $1$ 到 $n$。共有 $m$ 名参赛者，编号为 $1$ 到 $m$。

我们有一个长度为 $m$ 的数组 $a$，其中 $a_i$（$1 \leq a_i \leq n$）表示第 $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$ 中的值可以重复。所有可能的数组对 $(a, b)$ 共有 $n^m \cdot 2^m$ 种。

考虑所有满足“无人沮丧放弃”的数组对 $(a, b)$。对每一对这样的 $(a, b)$，计算所有参赛者疯狂值之和。求出所有这些和的总和。

题目将给出一个质数模数 $p$。请输出该总和对 $p$ 取模的结果。

The only line contains three integers $n$, $m$, $p$ ($1 \leq m \leq n \leq 500, 10^8 \leq p \leq 10 ^ 9 + 9$).

It is guaranteed, that the number $p$ is prime.

唯一一行包含三个整数 $n$、$m$、$p$（$1 \leq m \leq n \leq 500$，$10^8 \leq p \leq 10 ^ 9 + 9$）。

保证 $p$ 是一个质数。

Print only one integer — the required sum by modulo $p$.

仅输出一个整数——对 $p$ 取模后的所需和。

In the first test, there are three possible arrays $a$: ${1}$, ${2}$, and $ {3}$ and two possible arrays $b$: ${\mathtt{L}}$ and ${\mathtt{R}}$. For all six pairs of arrays $(a, b)$, the only participant will sit behind the computer $a_1$, so his madness will be $0$. So the total sum of madnesses will be $0$.

In the second test, all possible pairs of arrays $(a, b)$, such that no person becomes upset are:

• $({1, 1}, {\mathtt{L}, \mathtt{L}})$, the sum of madnesses is $1$;
• $({1, 1}, {\mathtt{R}, \mathtt{L}})$, the sum of madnesses is $1$;
• $({2, 2}, {\mathtt{R}, \mathtt{R}})$, the sum of madnesses is $1$;
• $({2, 2}, {\mathtt{L}, \mathtt{R}})$, the sum of madnesses is $1$;
• all possible pairs of $a \in {{1, 2}, {2, 1}}$ and $b \in {{\mathtt{L}, \mathtt{L}}, {\mathtt{R}, \mathtt{L}}, {\mathtt{L}, \mathtt{R}}, {\mathtt{R}, \mathtt{R}}}$, the sum of madnesses is $0$.

So, the answer is $1 + 1 + 1 + 1 + 0 \ldots = 4$.

在第一个测试用例中，有三种可能的数组 $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$。