Background

Original problem link: https://oier.team/problems/S2C。

Jump Jump is world No. 1.

No coaching, no apprentices. Find the gap by yourself.

Problem Description

Given a number line with positions from $1$ to $n$. From each position $i$, you can jump to $i+1$ (if $i+1\le n$), or to $i-1$ (if $i-1\ge 1$), or to one of its divisors. Each position can be visited at most once. Ask how many different ways there are to go from position $n$ to position $1$. Output the answer modulo $p$。

Two ways are different if and only if there exists a jump after which the landing position is different, or there exists a jump whose type is different.

Input Format

One line with two integers $n,p$。

Output Format

One line with one integer, the answer modulo $p$。

3 1000000007

3

4 1000

7

100 511609

272799

Hint

[Sample Explanation #1]

Let $\rightarrow$ denote jumping up or down by $1$, and $\Rightarrow$ denote jumping to a divisor. There are $3$ ways in total, as follows.

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

[Sample Explanation #2]

Let $\rightarrow$ denote jumping up or down by $1$, and $\Rightarrow$ denote jumping to a divisor. There are $7$ ways in total, 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$

[Constraints]

This problem uses bundled testdata.

• 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): no special constraints。

For all testdata, $1\le n\le5\times10^3$, $2\le p\le 10^9+7$。

Input Format

One line with two integers $n,p$。

Output Format

One line with one integer, the answer modulo $p$。

Translated by ChatGPT 5