3065. [HSOI 2018] HS的棋盘

【题目描述】

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

(1) 每一行都至少摆放有两个卒

(2） 任意两个卒都不会互相攻击

hs现在想知道，满足上述条件，有多少种摆放卒的方案？由于答案可能很大，你只需输出方案数对 P 取模的结果即可。 两种方案被认为不同当且仅当存在同一格点的摆放情况不同。

【输入格式】

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

【输出格式】

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

【样例输入1】

2 1000000000

【样例输出1】

1

【样例输入2】

7 1000000000

【样例输出2】

612231936

【提示】

对于 20% 的数据， N≤100，P≤10^{9}

对于 50% 的数据， N≤10^5，P≤10^{9}

对于 100%的数据 ， N≤10^{18}，P≤10^{18}