Problem Description

Given an integer $ N $ and a prime number $ P $.

Find the number of connected undirected graphs with $ N $ vertices numbered from $ 1 $ to $ N $ that satisfy the following conditions, modulo $ P $.

• $ G $ has no self-loops. Multiple edges are allowed.
• For every edge $ (u,v) $ in $ G $, removing $ (u,v) $ from $ G $ still keeps $ G $ connected. That is, $ G $ is biconnected.
• For every edge $ (u,v) $ in $ G $, removing $ (u,v) $ from $ G $ makes $ G $ no longer biconnected.

Two graphs are considered different if and only if there exists a pair of vertices $ (u,v) $ such that the number of edges connecting $ u $ and $ v $ is different in the two graphs.

Input Format

The input is given from the standard input in the following format:

$ N $ $ P $

Output Format

Output the answer.

Sample Input and Output

Sample Input #1

2 1005976817

Sample Output #1

1

Sample Input #2

5 1000837403

Sample Output #2

372

Sample Input #3

10 1001160547

Sample Output #3

789846604

Sample Input #4

20 1006779551

Sample Output #4

888612770

Notes/Hints

Constraints

• $2 \le N \le 50$
• $10^9 < P < 1.01 \times 10^9$
• $ P $ is a prime number.
• All input values are integers.

见题面 Input 部分

见题面 Output 部分