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

跳跃

题目描述

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

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

输入格式

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

输出格式

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

输入输出样例 #1

输入 #1

3 1000000007

输出 #1

3

输入输出样例 #2

输入 #2

4 1000

输出 #2

7

输入输出样例 #3

输入 #3

100 511609

输出 #3

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$。