题目背景

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

题目描述

现在，gjm 脑海里有一个 $N \times N$ 的棋盘，其上共有 $N \times N$ 个格子， gjm 开始在棋盘上的格点上摆放卒，已知卒仅会攻击往左边一个格点和往右边一个格点上的棋子，现在 gjm 开始在棋盘上摆放任意多个卒，满足：

1. 每一行都至少摆放有两个卒
2. 任意两个卒都不会互相攻击

gjm 现在想知道，满足上述条件，有多少种摆放卒的方案？由于答案可能很大，你只需输出方案数对 $P$ 取模的结果即可。

两种方案被认为不同当且仅当存在同一格点的摆放情况不同。

输入格式

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

输出格式

一行一个整数，即在 $N \times 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：学无止境