AT_abc282_g [ABC282G] Similar Permutation

题目描述

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

对于两个排列 $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$ 取模后输出。

输入格式

输入为标准输入，格式如下：

$N$ $K$ $P$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

3 1 282282277

输出 #1

16

输入输出样例 #2

输入 #2

50 25 998244353

输出 #2

131276976

说明/提示

限制条件

• $2 \leq N \leq 100$
• $0 \leq K \leq N-1$
• $10^8 \leq P \leq 10^9$
• $P$ 是素数
• 输入均为整数

样例解释 1

例如，满足条件的一个排列对如下：

• $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$。

样例解释 2

请对个数取 $P$ 的余数后输出。

由 ChatGPT 4.1 翻译