시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 1 1 1 100.000%

문제

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.

예제 입력 1

1 100

예제 출력 1

0

예제 입력 2

10 100

예제 출력 2

68