19471번 - Parentheses 다국어

문제

A correct parentheses sequence can be 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.

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

For a parentheses sequence, you can make some operations with it.

• Each time you can choose two indices $L$ and $R$ such that $L \le R$. The operation modifies the characters on 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 specified range changes to a ')' and vice versa.

The value of a parentheses sequence is the minimal number of the operations required to change it into a correct parentheses sequence. If it is impossible, the value of the sequence is equal to 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 different parentheses sequence of length $n$ which has value $i,ドル and then calculate 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 of the input 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.

제한

힌트