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

On the first day, the tree grows a root node. On each subsequent day, the tree randomly selects a branch in the current tree that does not yet have a node growing from it, and a new node grows on this branch. An edge is then connected between the new node and the node to which the branch belongs.

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

He is now very curious: if Little G comes to his house to pick apples after $N$ days, what is the expected value $E$ of this inconvenience? 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

The input consists of two integers $N$ and $P$ on a single line.

Output

Output a single integer representing the answer.

Examples

Input 1

3 610745795

Output 1

24

Note 1

The figure below shows all possible apple tree configurations for $N = 3$, where the numbers indicate the day the node grew. It is clear that in each case, the sum of distances between all pairs of nodes is 4.

Input 2

See tree/tree2.in in the contestant directory.

Output 2

See tree/tree2.ans in the contestant directory.