相似排列

题目描述

下面,将 $(1,2,\ldots,N)$ 的排列简称为排列。

对于两个排列 $A=(A_1,A_2,\ldots,A_N)$ 和 $B=(B_1,B_2,\ldots,B_N)$,定义它们的相似度为满足以下条件的整数 $i$(介于 $1$ 和 $N-1$ 之间)的个数:

$(A_{i+1}-A_i)(B_{i+1}-B_i) \gt 0$。

求相似度为 $K$ 的排列对 $(A,B)$ 的个数,对素数 $P$ 取模。

输入格式

输入按以下格式从标准输入给出。

$N$ $K$ $P$

输出格式

输出答案。

样例

3 1 282282277

16

例如,下面是一对满足条件的排列。

$A=(1,2,3)$

$B=(1,3,2)$

此时有 $(A_2 - A_1)(B_2 -B_1) \gt 0$ 和 $(A_3 - A_2)(B_3 -B_2) \lt 0$,所以 $A$ 和 $B$ 的相似度为 $1$。

50 25 998244353

131276976

对 $P$ 取模后输出。

数据范围

• $2 \le N \le 100$
• $0 \le K \le N-1$
• $10^8 \le P \le 10^9$
• $P$ 是素数。
• 输入中的所有值都是整数。