P5059 Chinese Chess.

gjm really likes studying board game problems. Recently, he has been researching Chinese chess QwQ.

Now, in gjm’s mind there is an $N \times N$ chessboard, with a total of $N \times N$ cells. gjm starts placing pawns on the grid points of the board. It is known that a pawn only attacks pieces on the grid point one step to its left and one step to its right. Now gjm places any number of pawns on the board, satisfying: 1. Each row has at least two pawns placed. 2. No two pawns attack each other. gjm now wants to know: how many pawn placement schemes satisfy the above conditions? Since the answer may be very large, you only need to output the number of schemes modulo $P$. Two schemes are considered different if and only if there exists at least one grid point where the placement differs.

One line with two positive integers, $N$ and $P$.

One line with one integer, the number of pawn placement schemes on an $N \times N$ board modulo $P$.

**Explanation for Sample 1** Obviously, there is no valid scheme. **Explanation for Sample 2** ($0$ means no pawn on the grid point, $1$ means there is a pawn on the grid point.) There is only one scheme: $1$ $0$ $1$ $1$ $0$ $1$ $1$ $0$ $1$ This sample and its explanation are correct. **Explanation for Sample 3** It is too large to list all schemes, so no explanation is given. Constraints: For $20\%$ of the testdata, $N \le 100$, $P \le 10^{9}$. For $50\%$ of the testdata, $N \le 10^5$, $P \le 10^{9}$. For $100\%$ of the testdata, $N \le 10^{18}$, $P \le 10^{18}$. By: Endless Learning. Translated by ChatGPT 5