P10812 [MX-S2-T3] Jump

Original problem link: 。 ---  ~~Jump Jump is world No. 1.~~ ~~No coaching, no apprentices. Find the gap by yourself.~~

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.

One line with two integers $n,p$。

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

**[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