当前没有测试数据。

G - 相似排列

得分： $600$ 分

问题描述

对于两个排列 $A=(A_1,A_2,\ldots,A_N),B=(B_1,B_2,\ldots,B_N)$，我们定义它们的相似度为满足 $1$ 到 $N-1$ 之间的整数 $i$ 个数，满足：

• $(A_{i+1}-A_i)(B_{i+1}-B_i)>0$。

计算满足相似度为 $K$ 的排列对 $(A,B)$ 的数量，对 $P$ 取模。

约束条件

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

输入

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

$N$ $K$ $P$

输出

输出答案。

3 1 282282277

16

例如，以下是满足条件的排列对。

• $A=(1,2,3)$
• $B=(1,3,2)$

在此排列对中，满足 $(A_2 - A_1)(B_2 -B_1) > 0$ 和 $(A_3 - A_2)(B_3 -B_2) < 0$，所以 $A$ 和 $B$ 的相似度为 $1$。

50 25 998244353

131276976

输出结果对 $P$ 取模。