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

    ID: 13084 远端评测题 5000ms 512MiB 尝试: 0 已通过: 0 难度: 6 上传者: 标签>递推2019组合数学容斥原理生成函数高斯消元PA(波兰)

[PA 2019 Final] 数图 / Grafy

题目背景

译自 PA 2019 Final。5s,256M\texttt{5s,256M}

本题数据为自造。

std: joke3579,validator & generator: Starrykiller。

加强版:P11821。请勿提交 OEIS 题解。

题目描述

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

  • 1in\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 取模后的结果。

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

输入格式

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

输出格式

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

4 1000000007
9

提示

  • 3n5003\le n\le 500
  • 108+7p109+710^8+7\le p\le 10^9+7pp 为素数。