P5059 中国象棋

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

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

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

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

**样例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：学无止境