题目背景

$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 :$ 学无止境