Parentheses

A correct parentheses sequence is defined recursively as follows:

• The empty string is a correct sequence.
• If $X$ and $Y$ are correct sequences, then $X Y$ (the concatenation of $X$ and $Y$) is a correct sequence.
• If $X$ is a correct sequence, then $`(`X`)`$ is a correct sequence.

Every correct parentheses sequence can be derived using the rules above.

For a parentheses sequence, you can perform some operations on it.

• Each time, choose two indices $L$ and $R$ such that $L \le R$. The operation modifies the characters at indices from $L$ to $R$, inclusive.
• First, the order of these characters is reversed.
• Then, each character is toggled to the opposite one. That is, each '(' in the range becomes ')' and each ')' becomes '('.

The value of a parentheses sequence is the minimum number of operations required to change it into a correct parentheses sequence. If it is impossible, the value is $10^{100}$.

For example, the value of "()((" is $1$, the value of "()()" is $0$, and the value of "(((" is $10^{100}$.

You are given an integer $n$. For each $1 \le i \le n$, find the number $A_i$ of distinct parentheses sequences of length $n$ whose value is $i$, then compute the sum $\sum_{i = 0}^{n} ((i + 1) \cdot A_i)$.

The answer may be very large, so print it modulo the given integer $m$.

The first line contains two integers $n$ and $m$ ($1 \le n \le 10^6$, $1 \le m \le 10^9$).

Print one integer: the answer to the problem.