9160: ABC281 —— G - Farthest City
[Creator : ]
Description
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.
- 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$.
Here, the shortest distance from vertex $u$ to vertex $v$ is the minimum number of edges in a simple path connecting vertices $u$ and $v$.
Two 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.
Find the number, modulo $M$, of simple connected undirected graphs with $N$ vertices numbered $1, \dots, N$ that satisfy the following condition.
- 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$.
Here, the shortest distance from vertex $u$ to vertex $v$ is the minimum number of edges in a simple path connecting vertices $u$ and $v$.
Two 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.
Input
The input is given from Standard Input in the following format:
```
$N$ $M$
```
```
$N$ $M$
```
Output
Print the answer.
Constraints
- $3 \leq N \leq 500$
- $10^8 \leq M \leq 10^9$
- $N$ and $M$ are integers.
- $10^8 \leq M \leq 10^9$
- $N$ and $M$ are integers.
Sample 1 Input
4 1000000000
Sample 1 Output
8
The following eight graphs satisfy the condition.
Sample 2 Input
3 100000000
Sample 2 Output
1
Sample 3 Input
500 987654321
Sample 3 Output
610860515
HINT
相同题目：ABC281。