For all rooted trees with $n$ nodes, calculate the sum of their heights. The answer should be taken modulo $p$.

The height is defined as the length of the longest simple path starting from the root.

Two rooted trees are considered equal if and only if they have the same number of children for the root, and their corresponding subtrees (ordered from left to right) are equal.

Input

The input consists of two integers $n$ and $p$.

Output

Output the sum of the heights of all rooted trees with $n$ nodes, modulo $p$.

Examples

Input 1

4 998244353

Output 1

10

Note 1

For Example 1:

• There is $1$ tree of height $1$: the root has $3$ children directly.
• There are $3$ trees of height $2$:
  • One child, which has two children of its own.
  • Two children, where one is a leaf. This counts as two distinct configurations because the children are ordered (the first child is a leaf, or the second child is a leaf).
• There is $1$ tree of height $3$: a single chain.

Input 2

10 998244353

Output 2

19838

Input 3

514 998244353

Output 3

867876856

Subtasks

For the first $20\%$ of the data, $n\le 50$.

For the first $40\%$ of the data, $n\le 400$.

For the first $60\%$ of the data, $n\le 1000, p = 998244353$.

For the first $80\%$ of the data, $n\le 2000$.

For $100\%$ of the data, $1\le n\le 10^5, 9\times 10^8 \le p\le 1.01 \times 10^9$, and $p$ is a prime number.