#P18250. Balance in All Things

Balance in All Things

Balance in All Things

题目描述

Bobo 正在参加一个奇怪的比赛,共有 2n 名选手,编号依次为 1,2,…,2n。所有选手的初始积分均为 0。

比赛共进行 k 轮。每轮将所有选手两两配对,每名选手恰好参加一场比赛。每场比赛的积分变化如下:

  • 如果两人的积分不同,积分较高者减 1 分,积分较低者加 1 分。
  • 如果两人的积分相同,编号较小者加 1 分,另一人减 1 分。

主办方要求:在整个比赛过程中,任何选手积分的绝对值都不能超过 3。

请计算这 k 轮比赛共有多少种合法的配对安排。选手有不同编号,轮次有先后顺序;一轮中的每一对不区分顺序,各场比赛之间也不区分排列顺序。

答案可能很大,请输出对指定质数 P 取模的结果。

输入格式

第一行包含三个整数 n,k,P。

输出格式

输出一行一个整数,表示合法安排数量对 P 取模的结果。

数据范围

  • 1≤n≤400。
  • 1≤k≤20。
  • 100000000≤P≤1000000009。
  • 保证 P 是质数。

样例 1

3 1 1000000007
15

样例 2

100 3 1000000007
894710378

样例 3

6 6 1000000007
103387851

样例 4

2 6 998244353
729