{"raw_statement":[{"iden":"problem statement","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 condition:\n\n*   For every spanning tree $T$ of $G$, there is a perfect matching in $T$.\n\nWhat 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."},{"iden":"constraints","content":"*   $2 \\leq N \\leq 500$\n*   $10^8 \\leq M \\leq 10^9$\n*   $N$ is even.\n*   $M$ is prime.\n*   All input values are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$ $M$"},{"iden":"sample input 1","content":"4 998244353"},{"iden":"sample output 1","content":"15\n\nFor 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.\n![image](https://img.atcoder.jp/agc065/2ef467c5e79ec3372986afd95c28100a.png)"},{"iden":"sample input 2","content":"10 998244353"},{"iden":"sample output 2","content":"128792160"},{"iden":"sample input 3","content":"300 923223991"},{"iden":"sample output 3","content":"359143490"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}