#P13965. [PA 2019 Final] 数图 / Grafy

    ID: 13177 传统题 5000ms 256MiB 尝试: 2 已通过: 1 难度: 9 上传者: 标签>CF2600组合数学计数DP模运算数学生成函数

[PA 2019 Final] 数图 / Grafy

题目描述

求出 nn 个节点的满足以下条件的有标号有向简单图的数量:

  • ∀1≤i≤n\forall 1\le i\le n,$\operatorname{deg_{out}}(i)=\operatorname{deg_{in}}(i)=2$。

这里,degout⁡(u)\operatorname{deg_{out}}(u) 指节点 uu 的出度,degin⁡(u)\operatorname{deg_{in}}(u) 指节点 uu 的入度。

你只需要输出答案对给定大素数 pp 取模后的结果。

注意我们是对有标号的「有向简单图」计数。也就是说,这张图中无重边自环。注意 u→vu\to v 和 v→uv\to u 同时出现是允许的。

输入格式

一行两个正整数 n,pn,p。

输出格式

一行一个非负整数,表示答案。

输入输出样例 #1

输入 #1

4 1000000007

输出 #1

9

说明/提示

  • 3≤n≤5003\le n\le 500;
  • 108+7≤p≤109+710^8+7\le p\le 10^9+7,pp 为素数。