Problem Background

HAOI2018 Round2 Question 1

Problem Description

Little C has planted an apple tree in his garden, where each node has exactly two branches. Through careful observation, Little C has found that every day, the tree grows a new node.

On the first day, the tree grows a root node. From the second day onwards, the tree randomly selects a branch that has not yet grown a node, and grows a new node on this branch. A new edge is connected between the new node and the node to which the branch belongs.

Little C defines the inconvenience of the tree as the sum of the distances between all pairs of nodes on the tree. The distance between two nodes is defined as the number of edges traversed on the path from one node to the other.

Now, Little C is curious about what the expected inconvenience \( E \) will be after \( N \) days when Little G comes to pick apples. However, Little C dislikes fractions, so he only wants to know the result of \( E \times N! \) modulo \( P \). It can be proven that this is an integer.

Input Format

Read data from standard input. One line with two integers \( N \) and \( P \).

Output Format

Output to standard output. Output an integer representing the answer.

Sample Input and Output

Sample Input #1

3 610745795

Sample Output #1

24

Sample Input #2

305 1000000007

Sample Output #2

865018107

Notes

The above image shows all possible apple tree shapes for \( N = 3 \), where the numbering indicates the day on which the node was grown. Clearly, the distance between any two nodes in each case is 4.

Data Range and Constraints

见题面 Input 部分

见题面 Output 部分