中国象棋

$ gjm $ 非常喜欢研究棋类问题，最近，他在钻研中国象棋 $QwQ$

现在，$ gjm $ 脑海里有一个 $ N $ × $ N $ 的棋盘，其上共有 $ N $ × $ N $个格子，$ gjm $ 开始在棋盘上的格点上摆放卒，已知卒仅会攻击往左边一个格点和往右边一个格点上的棋子，现在 $ gjm $ 开始在棋盘上摆放任意多个卒，满足： $(1)$ 每一行都至少摆放有两个卒 $(2)$ 任意两个卒都不会互相攻击 $ gjm $ 现在想知道，满足上述条件，有多少种摆放卒的方案？由于答案可能很大，你只需输出方案数对 $ P $ 取模的结果即可。 两种方案被认为不同当且仅当存在同一格点的摆放情况不同。

一行两个正整数，分别为$ N $ 和 $ P $。

一行一个整数，即在$ N $ × $ N $ 棋盘中摆放卒的方案数对 $ P $ 取模的结果 。

1 10007

0

2 1000000000

1

7 1000000000

612231936

**样例1解释** 很明显没有方案 **样例2解释** ($0$ 表示格点上无卒，$1$ 表示格点上有卒) 仅有一种方案 $1$ $0$ $1$ $1$ $0$ $1$ $1$ $0$ $1$ 该样例以及解释无误 **样例3解释** 太大了无法列出所有方案，故不予解释 对于 $ 20 $% 的数据， $ N≤100$，$P≤10^{9}$ 对于 $ 50 $% 的数据， $ N≤10^5$，$P≤10^{9}$ 对于 $ 100 $%的数据 ， $ N≤10^{18}$，$P≤10^{18}$ $By : $ 学无止境