{"problem":{"name":"Farthest City","description":{"content":"You are given positive integers $N$ and $M$.   Find the number, modulo $M$, of simple connected undirected graphs with $N$ vertices numbered $1, \\dots, N$ that satisfy the following condition. *   Fo","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":4000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc281_g"},"statements":[{"statement_type":"Markdown","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.\n\n## Constraints\n\n*   $3 \\leq N \\leq 500$\n*   $10^8 \\leq M \\leq 10^9$\n*   $N$ and $M$ are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $M$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc281_g","tags":[],"sample_group":[["4 1000000000","8\n\nThe following eight graphs satisfy the condition.\n![image](https://img.atcoder.jp/abc281/5c77dfe15dfa3c03666e654bf8cfdc01.png)"],["3 100000000","1"],["500 987654321","610860515\n\nBe sure to find the number modulo $M$."]],"created_at":"2026-03-03 11:01:14"}}