Inconvenient Apple Tree

Little C has planted an apple tree in his garden. The tree is a full binary tree in the sense that every node has exactly two branches (each of which may eventually grow a new node). The tree grows in the following way:

1. On day 1, a single root node appears.
2. On each subsequent day, the tree randomly chooses one of the "free" branches (i.e. a branch that has never produced a node) from the current tree and grows a new node on that branch; an edge is added between the new node and the node whose branch was used. Since every node comes with exactly 2 branches when it appears, a new node always contributes 2 new free branches while consuming the branch on which it was attached.

The inconvenience of a tree is defined as the sum of distances between every pair of nodes. (The distance between two nodes is the number of edges on the unique simple path connecting them.)

Little C is curious about the expected inconvenience E of his tree after N days. However, he hates fractions so he decides to compute and output the value of E × N! modulo an integer P (it can be shown that E × N! is always an integer).

Note: The randomness in the tree‐growth process is as follows: on day 1 the tree has one node (with 2 free branches). Then on each day from 2 to N, among the current free branches the process picks one uniformly at random and grows a new node on it.

Input example: The input consists of two integers N and P on one line.

inputFormat

The first line of input contains two integers N (the number of days) and P (the modulus).

outputFormat

Output one integer, which is E × N! modulo P.

sample

1 100

0