该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

跳一跳世界第一。

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

题目描述

给定一个坐标轴，范围是 $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

样例 1 解释

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

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

4 1000

7

样例 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$

100 511609

272799

数据范围

本题采用捆绑测试。

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

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