Description

Xiao C planted an apple tree in his garden. Every node on the tree has exactly two branches. After careful observation, Xiao C found that each day the tree grows exactly one new node.

On the first day, the tree grows a root node. On every subsequent day, the tree randomly chooses one branch in the current tree that has not yet produced a node, and grows a new node on that branch. The new node is connected by an edge to the node that the branch belongs to.

Xiao C defines the “inconvenience” of an apple tree as the sum of distances between all pairs of nodes on the tree. The distance between two nodes is defined as the number of edges on the path from one to the other.

He is very curious: if Xiao G comes to pick apples after $N$ days, what is the expected inconvenience $E$? However, Xiao C hates 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 from standard input. A single line contains two integers $N$, $P$.

Output Format

Print to standard output. Output a single integer representing the answer.

3 610745795

24

305 1000000007

865018107

Hint

The above shows all possible apple tree shapes when $N = 3$, where the label on each node indicates the day on which it grew. Clearly, in every case the sum of pairwise node distances is $4$.

Constraints

Translated by ChatGPT 5