Background

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

Problem Description

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.

Input Format

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

Output Format

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

1 10007

0

2 1000000000

1

7 1000000000

612231936

Hint

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