题目背景

跳一跳世界第一。

不处，不收徒，差距自己找。

题目描述

给定一个坐标轴，范围是 $1\sim n$。每个点 $i$ 可以跳到 $i+1$（$i+1\le n$）或 $i-1$（$i-1\ge 1$）或他的因子处。每个点只能到达一次。问从点 $n$ 到点 $1$ 一共有多少方案。答案对 $p$ 取模。

两种方案不同当且仅当存在一次跳跃后的位置不同或存在一次跳跃的种类不同。

输入格式

一行两个整数 $n,p$。

输出格式

一行一个整数，表示答案对 $p$ 取模后的结果。

3 1000000007

3

4 1000

7

100 511609

272799

提示

【样例解释 #1】

设 $\rightarrow$ 表示向上或向下跳，$\Rightarrow$ 表示跳因子。共三种方案如下。

• $3\Rightarrow1$
• $3\rightarrow2\rightarrow1$
• $3\rightarrow2\Rightarrow1$

【样例解释 #2】

设 $\rightarrow$ 表示向上或向下跳，$\Rightarrow$ 表示跳因子。共七种方案如下。

• $4\rightarrow3\Rightarrow1$
• $4\rightarrow3\rightarrow2\rightarrow1$
• $4\rightarrow3\rightarrow2\Rightarrow1$
• $4\Rightarrow2\rightarrow3\Rightarrow1$
• $4\Rightarrow2\rightarrow1$
• $4\Rightarrow2\Rightarrow1$
• $4\Rightarrow1$

【数据范围】

本题采用捆绑测试。

• Subtask 0（8 pts）：$n\le20$。
• Subtask 1（11 pts）：$n\le150$。
• Subtask 2（23 pts）：$n\le300$。
• Subtask 3（26 pts）：$n\le1000$。
• Subtask 4（32 pts）：无特殊限制。

对于所有测试数据，$1\le n\le5\times10^3$，$2\le p\le 10^9+7$。