题目描述

题目译自 PA 2019 Final Grafy

你的任务是计算具有 $n$ 个顶点（编号为从 $1$ 到 $n$ 的整数）的有向图数量，其中每个顶点的入度和出度均为 $2$。

我们只考虑简单图，即不包含自环和重边的图，但可以同时包含边 $a \rightarrow b$ 和 $b \rightarrow a$。两个图被认为是不同的，当且仅当存在至少一对有序顶点对 $(a, b)$，使得边 $a \rightarrow b$ 在这两个图中仅存在于其中一个图中。

由于这类图的数量可能非常大，你只需要输出其数量除以给定的质数 $p$ 的余数。

输入格式

输入的唯一一行包含两个整数 $n$ 和 $p$（$3 \leq n \leq 500$；$10^{8}+7 \leq p \leq 10^{9}+7$；$p$ 是一个质数）。

输出格式

输出应包含一个整数，表示所求图的数量对 $p$ 取模的结果。

4 1000000007

9

对于 $n=4$，存在 $9$ 个满足任务条件的图。