题目描述

给定整数 $N,\ M$。请计算满足以下条件的长度为 $N$ 的序列 $A=[A_1,\ A_2,\ \ldots,\ A_N]$ 的个数。

• $2 \leq A_i \leq M$（$1 \leq i \leq N$）。
• 存在一个 $1$ 到 $N$ 的整数的排列 $P=[P_1,P_2,\ldots,P_N]$，使得对于 $1$ 到 $N$ 的每个 $i$，$A_i$ 等于序列 $[P_1,\ P_2,\ \ldots,\ P_{i-1},\ P_{i+1},\ \ldots,\ P_N]$ 的最长上升子序列的长度。

由于答案可能非常大，请输出其对素数 $Q$ 取模的结果。

输入格式

输入为一行，格式如下：

$N$ $M$ $Q$

输出格式

输出答案对 $Q$ 取模后的结果。

输入输出样例 #1

输入 #1

3 2 686926217

输出 #1

1

输入输出样例 #2

输入 #2

4 3 354817471

输出 #2

9

输入输出样例 #3

输入 #3

5 2 829412599

输出 #3

1

输入输出样例 #4

输入 #4

5 3 975576997

输出 #4

23

输入输出样例 #5

输入 #5

69 42 925171057

输出 #5

801835311

说明/提示

限制条件

• $3 \leq N \leq 5000$
• $2 \leq M \leq N-1$
• $10^8 \leq Q \leq 10^9$
• $Q$ 是素数。

样例解释 1

满足条件的序列只有 $[2, 2, 2]$。此时存在排列 $[1, 2, 3]$ 满足题意。

样例解释 2

满足条件的序列有以下 $9$ 个：$[2, 2, 2, 2]$，$[2, 2, 2, 3]$，$[2, 2, 3, 2]$，$[2, 2, 3, 3]$，$[2, 3, 2, 2]$，$[2, 3, 3, 2]$，$[3, 2, 2, 2]$，$[3, 3, 2, 2]$，$[3, 3, 3, 3]$。

样例解释 3

满足条件的序列只有 $[2, 2, 2, 2, 2]$。