#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