题目背景

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

本题数据为自造。

std: joke3579，validator & generator: Starrykiller。

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

题目描述

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

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

这里，$\operatorname{deg_{out}}(u)$ 指节点 $u$ 的出度，$\operatorname{deg_{in}}(u)$ 指节点 $u$ 的入度。

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

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

输入格式

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

输出格式

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

4 1000000007

9

提示

• $3\le n\le 500$；
• $10^8+7\le p\le 10^9+7$，$p$ 为素数。