#5516. 「PA 2019 Final」Grafy

标签: 传统 | 时间限制: 5000 ms | 内存限制: 256 MiB |

题目描述

你的任务是计算具有 $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

输出

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