题目描述

给定整数 $N,K$ 和素数 $P$。请计算满足以下所有条件的 $N$ 个顶点的有向图 $G$ 的个数，并输出其对 $P$ 取模的结果。注意，顶点之间是有区分的。

• $G$ 是一个竞赛图。也就是说，$G$ 中没有重边和自环，对于 $G$ 的任意两个不同顶点 $u,v$，恰好存在 $u \to v$ 或 $v \to u$ 其中之一的有向边。
• $G$ 中每个顶点的入度都不超过 $K$。
• 对于 $G$ 的任意四个不同的顶点 $a,b,c,d$，不存在 $a\to b,\ b\to c,\ c\to a,\ a\to d,\ b\to d,\ c\to d$ 这 $6$ 条边全部同时存在的情况。

输入格式

输入包含一行，格式如下：

$N$ $K$ $P$

输出格式

输出满足条件的有向图的个数对 $P$ 取模的结果。

样例 1

输入

4 3 998244353

输出

56

样例 2

输入

7 3 998244353

输出

720

样例 3

输入

50 37 998244353

输出

495799508

说明/提示

限制

• $4 \leq N \leq 200$
• $\frac{N-1}{2} \leq K \leq N-1$
• $10^8 < P < 10^9$
• $N,K$ 为整数
• $P$ 为素数

样例解释 1

在 $4$ 个顶点的图中，共有 $64$ 个锦标赛图，其中有 $8$ 个包含被禁止的诱导子图，剩下 $56$ 个满足条件。

由 ChatGPT 4.1 翻译