Tree

Kujou Karen is a girl who loves trees. She wants to generate two trees, each with $n$ nodes.

The generation method for the first tree is: 1. Node $1$ is the root of the tree. 2. For $i \in [2, n]$, choose a node from $[1, i - 1]$ as the parent of $i$.

The generation method for the second tree is: 1. Node $n$ is the root of the tree. 2. For $i \in [1, n - 1]$, choose a node from $[i + 1, n]$ as the parent of $i$.

Kujou Karen wants that for any $i \in [1, n]$, if node $i$ is a leaf in the first tree, then node $i$ must be a non-leaf in the second tree; if node $i$ is a non-leaf in the first tree, then node $i$ must be a leaf in the second tree. A node is called a leaf if and only if no other node has it as its parent.

Kujou Karen wants you to count the number of ways to generate these two trees. Specifically, you need to calculate the number of ways for all $n \in [2, N]$. Two ways are considered different if and only if there exists a node $i$ in one of the trees such that its parent is different in the two ways. Since the answer can be very large, you only need to output the result modulo $M$.

Input

The first line contains two integers $N$ and $M$, representing the upper bound of the number of nodes and the modulus, respectively.

Output

Output $N - 1$ lines, each containing one integer. Specifically, the $i$-th line should output the answer for $n = i + 1$ modulo $M$.

Examples

Input 1

(See the provided tree_ex1.in)

Output 1

(See the provided tree_ex1.ans)

Input 2

(See the provided tree_ex2.in)

Output 2

(See the provided tree_ex2.ans)

Constraints

For all test cases: $10 \le M \le 2^{30}$. The specific constraints for each test case are as follows: