Labeled Connected Graphs

Time limit2sMemory limit512 MB

Summary

Sum the distance between vertices 1 and 2 over every labeled connected graph on n vertices, modulo a prime m.

Level: Hard9 of 10
Topics: Combinatorics, Dynamic programming, Math, Graph
Solved: No attempts yet

Problem

You are given an integer $n$ and a prime modulo $m$ .

Calculate the sum of distances between the first and the second vertices over all distinct labeled connected graphs with $n$ vertices.

Output any integer congruent to the actual sum modulo $m$ . Formally, if the actual sum is $S$ , output any integer $x$ such that $-2^{63} \leq x < 2^{63}$ and $x - S$ is divisible by $m$ .

Input

The only line contains two integers $n$ and $m$ ( $2 \leq n \leq 400$ , $10^6 + 3 \leq m \leq 10^9+9$ , $m$ is prime), the number of vertices in the graphs and the modulo.

Output

Print a single integer: the answer to the problem.

Hint

If you manage to get WA in this problem and we reasonably believe that you did not intentionally try to do so, we might give you a cookie somehow.

Examples5

Example 1
Input
```
2 998244353
```
Expected output
```
1
```
Example 2
Input
```
3 1001177
```
Expected output
```
5
```
Example 3
Input
```
4 1000003
```
Expected output
```
54
```
Example 4
Input
```
5 1000159
```
Expected output
```
1108
```
Example 5
Input
```
6 1000253
```
Expected output
```
41880
```