{"raw_statement":[{"iden":"problem statement","content":"You are given positive integers $N$ and $M$.  \nFind the number, modulo $M$, of simple connected undirected graphs with $N$ vertices numbered $1, \\dots, N$ that satisfy the following condition.\n\n*   For every $u = 2, \\dots, N-1$, the shortest distance from vertex $1$ to vertex $u$ is strictly smaller than the shortest distance from vertex $1$ to vertex $N$.\n\nHere, the shortest distance from vertex $u$ to vertex $v$ is the minimum number of edges in a simple path connecting vertices $u$ and $v$.  \nTwo graphs are considered different if and only if there are two vertices $u$ and $v$ that are connected by an edge in exactly one of those graphs."},{"iden":"constraints","content":"*   $3 \\leq N \\leq 500$\n*   $10^8 \\leq M \\leq 10^9$\n*   $N$ and $M$ 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 1000000000"},{"iden":"sample output 1","content":"8\n\nThe following eight graphs satisfy the condition.\n![image](https://img.atcoder.jp/abc281/5c77dfe15dfa3c03666e654bf8cfdc01.png)"},{"iden":"sample input 2","content":"3 100000000"},{"iden":"sample output 2","content":"1"},{"iden":"sample input 3","content":"500 987654321"},{"iden":"sample output 3","content":"610860515\n\nBe sure to find the number modulo $M$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}