Always Perfect

AtCoder

IDagc065_f

Time2000ms

Memory256MB

Difficulty—

You are given an even number $N$ and a prime number $M$. Find the number, modulo $M$, of simple connected undirected graphs $G$ with $N$ vertices numbered $1$ to $N$ that satisfy the following condition: * For every spanning tree $T$ of $G$, there is a perfect matching in $T$. What is a perfect matching in a graph? For a graph $G$, a set of edges $E$ from $G$ is called a perfect matching in $G$ if, for every vertex $v$ in the graph, $E$ contains exactly one edge with $v$ as an endpoint. ## Constraints * $2 \leq N \leq 500$ * $10^8 \leq M \leq 10^9$ * $N$ is even. * $M$ is prime. * All input values are integers. ## Input The input is given from Standard Input in the following format: $N$ $M$ [samples]

Samples

Input #1

4 998244353

Output #1

15

For example, among the two graphs shown in the figure below, the graph on the left satisfies the condition. On the other hand, the graph on the right does not because there is no perfect matching in the spanning tree with the three edges shown in bold red.
![image](https://img.atcoder.jp/agc065/2ef467c5e79ec3372986afd95c28100a.png)

Input #2

10 998244353

Output #2

128792160

Input #3

300 923223991

Output #3

359143490

API Response (JSON)

{
  "problem": {
    "name": "Always Perfect",
    "description": {
      "content": "You are given an even number $N$ and a prime number $M$. Find the number, modulo $M$, of simple connected undirected graphs $G$ with $N$ vertices numbered $1$ to $N$ that satisfy the following conditi",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "agc065_f"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given an even number $N$ and a prime number $M$.\nFind the number, modulo $M$, of simple connected undirected graphs $G$ with $N$ vertices numbered $1$ to $N$ that satisfy the following conditi...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments