Problem Background

$ gjm $ loves studying chess problems very much. Recently, he has been researching Chinese Chess $QwQ$.

Problem Description

Now, $ gjm $ has an $ N $ × $ N $ chessboard in his mind, with a total of $ N $ × $ N $ squares. $ gjm $ starts placing pawns on the grid points of the chessboard. It is known that a pawn only attacks the square to its left and the square to its right. Now, $ gjm $ starts placing any number of pawns on the chessboard, satisfying:

$(1)$ Each row has at least two pawns.

$(2)$ No two pawns can attack each other.

$ gjm $ now wants to know how many ways there are to place the pawns satisfying the above conditions. Since the answer may be very large, you only need to output the result of the number of schemes modulo $ P $.

Two schemes are considered different if and only if there is a different placement on the same grid point.

Input Format

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

Output Format

A line with one integer, the number of ways to place the pawns on the $ N $ × $ N $ chessboard modulo $ P $.

Sample Input and Output

Sample Input #1

1 10007

Sample Output #1

0

Sample Input #2

2 1000000000

Sample Output #2

1

Sample Input #3

7 1000000000

Sample Output #3

612231936

Notes

Sample 1 Explanation
Clearly, there is no solution.

Sample 2 Explanation (0 indicates no pawn, 1 indicates a pawn)

There is only one solution:

1 0 1

1 0 1

1 0 1

This sample and explanation are correct.

Sample 3 Explanation
Too large to list all solutions, so no explanation is provided.

For $20 \%$ of the data, $ N≤100 $, $ P≤10^{9} $.

For $50 \%$ of the data, $ N≤10^5 $, $ P≤10^{9} $.

For $100 \%$ of the data, $ N≤10^{18} $, $ P≤10^{18} $.

$By : $ 学无止境

见题面 Input 部分

见题面 Output 部分