分数: 600 点
问题陈述
下面是以下的排列 (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)>0.
求一个素数的模数 P,排列对 (A,B) 其相似度是 K.
约束
- 2\leq N \leq 100
- 0\leq K \leq N-1
- 10^8 \leq P \leq 10^9
- P 是素数。
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N K P
输出
打印答案。
示例输入 1
3 1 282282277
示例输出 1
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 is 1.
示例输入 2
50 25 998244353
示例输出 2
131276976
打印数字模数 P.