Non-Attacking Pawn Placements on an N x N Chessboard

Given an N × N chessboard, you are to place an arbitrary number of pawns (卒) on the grid cells with the following conditions:

• Each row must contain at least two pawns.
• No two pawns attack each other. A pawn can only attack the cell immediately to its left and the cell immediately to its right (in the same row).

Two configurations are considered different if there exists at least one cell that contains a pawn in one configuration and is empty in the other.

Output the total number of valid placements modulo \( P \).

Note: In a single row, the pawns must not be placed in consecutive cells (since if two pawns are adjacent, they would attack each other). Thus, for each row, we need to count all subsets of cells (from the N available) with no two consecutive cells, and with at least 2 cells chosen. The placements in different rows are independent.

If we denote by \( f(N) \) the number of ways to choose cells from a row such that no two chosen cells are consecutive (including the empty set and single cell choices), then \( f(N) = F_{N+2} \) where \( F \) is the standard Fibonacci sequence with \( F_1 = 1, F_2 = 1. \) Therefore, the number of valid placements in one row is \[ \text{rowWays} = f(N) - (1+N) \quad \text{(subtracting the number of ways that choose fewer than two cells)}. \] Since the rows are independent, the answer is given by \[ \text{answer} = (\text{rowWays})^N \pmod{P}. \]

inputFormat

The input consists of a single line containing two integers \( N \) and \( P \) (separated by a space):

• \( N \) is the dimension of the chessboard.
• \( P \) is the modulus.

outputFormat

Output a single integer, the number of valid placements modulo \( P \).

sample

1 10

0