Problem Background

Jump is number one in the world.

Not accepting apprentices, the gap is to be found by oneself.

Problem Description

Given a coordinate axis with a range of $1 \sim n$. Each point $i$ can jump to $i+1$ ($i+1 \le n$), $i-1$ ($i-1 \ge 1$), or to a factor of $i$. Each point can only be visited once. How many ways are there to go from point $n$ to point $1$? The answer should be taken modulo $p$.

Two schemes are considered different if and only if there is a different position after a jump or a different type of jump.

Input Format

One line containing two integers $n$ and $p$.

Output Format

One line containing an integer, representing the result modulo $p$.

Sample Input and Output

Sample Input #1

3 1000000007

Sample Output #1

3

Sample Input #2

4 1000

Sample Output #2

7

Sample Input #3

100 511609

Sample Output #3

272799

Notes

[Sample Explanation #1]

Let $\rightarrow$ denote a jump up or down, and $\Rightarrow$ denote a jump to a factor. There are three schemes as follows:
+ $3\Rightarrow1$
+ $3\rightarrow2\rightarrow1$
+ $3\rightarrow2\Rightarrow1$

[Sample Explanation #2]

Let $\rightarrow$ denote a jump up or down, and $\Rightarrow$ denote a jump to a factor. There are seven schemes as follows:
+ $4\rightarrow3\Rightarrow1$
+ $4\rightarrow3\rightarrow2\rightarrow1$
+ $4\rightarrow3\rightarrow2\Rightarrow1$
+ $4\Rightarrow2\rightarrow3\Rightarrow1$
+ $4\Rightarrow2\rightarrow1$
+ $4\Rightarrow2\Rightarrow1$
+ $4\Rightarrow1$

[Data Range]

This problem uses subtask testing.

• Subtask 0 (8 pts): $n \le 20$.
• Subtask 1 (11 pts): $n \le 150$.
• Subtask 2 (23 pts): $n \le 300$.
• Subtask 3 (26 pts): $n \le 1000$.
• Subtask 4 (32 pts): No special restrictions.

For all test data, $1 \le n \le 5 \times 10^3$, $2 \le p \le 10^9 + 7$.

见题面 Input 部分

见题面 Output 部分