传送机器题
题号：NC308042
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

\hspace{15pt}在数轴区间 [1,n] 上，初始时在集合 \Bbb S \left(\Bbb S \subseteq \{1,2,\dots,n\}\right) 的位置上存在传送器，你的起始位置为点 1。你可以进行无限轮操作，每一轮可以从以下三种方法中任选一种执行：
\hspace{23pt}\bullet\,方法一：向相邻整数位置移动；
\hspace{23pt}\bullet\,方法二：传送到任意一个已有传送器的位置；
\hspace{23pt}\bullet\,方法三：在当前位置修建一个新的传送器。
\hspace{15pt}最终要求在集合 \Bbb T \left(\Bbb S \subseteq \Bbb T \subseteq \{1,2,\dots,n\}\right) 的位置上存在传送器，并且你必须到达点 n。请计算达成该最终局面所需的最少操作轮数。

\hspace{15pt}为了便于输出，记 f(\Bbb S,\Bbb T) 为：初始传送器集合为 \Bbb S，经过操作后传送器位置集合恰好为 \Bbb T，且人到达点 n 时，所需的最小操作轮数。你需要计算：

\displaystyle\sum_{\Bbb T \subseteq \{1,2,\dots,n\}}\sum_{\Bbb S \subseteq \Bbb T} f(\Bbb S,\Bbb T) \bmod M

输入描述:

\hspace{15pt}在一行上输入两个整数 n, M \left(1 \leq n \leq 3 \times 10^3;\,10^8 \leq M \leq 10^9\right)，表示数轴区间长度、模数。

输出描述:

\hspace{15pt}在一行上输出一个整数，表示答案对 M 取模后的结果。
示例1

输入

复制 
1 998244353

输出

复制 
1
示例2

输入

复制 
2 998244353

输出

复制 
15
示例3

输入

复制 
3 998244353

输出

复制 
75

说明

\hspace{15pt}下面用长度为 n，仅由 0 和 1 组成的字符串来表示集合 \Bbb S、\Bbb T：（从左往右，下标从 1 开始）第 i 位为 1 表示集合中含有元素 i，第 i 位为 0 表示不含：
F(000,000)=2、F(000,001)=3、F(001,001)=1、F(000,010)=3
F(000,011)=4、F(001,011)=3、F(010,010)=2、F(010,011)=3
F(011,011)=1、F(000,100)=3、F(000,101)=4、F(001,101)=2
F(000,110)=4、F(000,111)=5、F(001,111)=4、F(010,110)=3
F(010,111)=4、F(011,111)=2、F(100,100)=2、F(100,101)=3
F(101,101)=1、F(100,110)=3、F(100,111)=4、F(101,111)=3
F(110,110)=2、F(110,111)=3、F(111,111)=1。
示例4

输入

复制 
5 998244353

输出

复制 
1167
示例5

输入

复制 
10 998244353

输出

复制 
561495
示例6

输入

复制 
1000 993244353

输出

复制 
153871200

备注: