← 返回题目列表

AtCoder · abc282_g

G. 类似排列

中文机器翻译题面 查看原题

分数: 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.