题目描述

题目译自 PA 2018 Runda 5 Skwarki。

求有多少种长度为 $N$ 的满足以下条件的序列：

• $1 \sim N$ 这 $N$ 个数在序列中各出现了一次；
• 至少进行 $K$ 次操作后，该序列才只含有 $1$ 个元素。

下面对操作进行描述：

设 $A_i$ 为序列中的第 $i$ 个元素（$1 < i < \mathrm{len}$，$\mathrm{len}$ 为序列长度），若 $A_{i-1} > A_{i}$ 或 $A_{i+1} > A_{i}$ 则标记 $A_i$。
若 $A_2 > A_1$ 则标记 $A_1$，
若 $A_{\mathrm{len}-1} > A_{\mathrm{len}}$ 则标记 $A_{\mathrm{len}}$。

然后，将有标记的元素从序列中删除。

满足条件的序列可能很多，所以请将结果对 $P$ 取模。

输入格式

输入仅一行，包含三个整数 $N,K,P$。

输出格式

输出一行一个整数，表示满足条件的序列个数对 $P$ 取模的结果。

样例

输入

5 3 100000007

输出

4

所有满足条件的序列列举如下：

• $(4,1,3,2,5)$
• $(4,2,3,1,5)$
• $(5,1,3,2,4)$
• $(5,2,3,1,4)$

数据范围与提示

$1 \le K,N \le 1000$，$N \ge 2$，$10^8 \le P \le 10^9$。