INOI 决赛座位

• 时间限制：3 秒
• 内存限制：256 MiB

题目描述

比赛教室中有一排 $n$ 台电脑，从左到右编号为 $1$ 到 $n$。有 $m$ 位参赛者依次进入教室。

第 $i$ 位参赛者选择目标电脑 $a_i$，并选择方向 $b_i$：

• L 表示从左侧进入并从左向右移动；
• R 表示从右侧进入并从右向左移动。

他先尝试坐在 $a_i$。若该电脑已被占用，就沿所选方向继续前进，坐到遇到的第一个空位；若沿该方向找不到空位，则该数组对 $(a,b)$ 不合法。

参赛者的疯狂值等于实际座位与目标座位的距离。对全部合法的 $n^m2^m$ 种候选数组对，求所有参赛者疯狂值之和的总和，并对给定质数 $p$ 取模。

输入格式

一行包含三个整数 $n,m,p$。

输出格式

输出所求总和对 $p$ 取模的结果。

样例输入 1

3 1 1000000007

样例输出 1

0

样例输入 2

2 2 1000000009

样例输出 2

4

样例输入 3

3 2 998244353

样例输出 3

8

样例输入 4

20 10 1000000009

样例输出 4

352081045

数据范围

对于全部数据，$1\le m\le n\le500$，$10^8\le p\le10^9+9$，且 $p$ 为质数。

题目来源：Codeforces 1439D。