A14371. Up the Strip

Note that the memory limit in this problem is lower than in others.

You have a vertical strip with $n$ cells, numbered consecutively from $1$ to $n$ from top to bottom.

You also have a token that is initially placed in cell $n$ . You will move the token up until it arrives at cell $1$ .

Let the token be in cell $x > 1$ at some moment. One shift of the token can have either of the following kinds:

- Subtraction: you choose an integer $y$ between $1$ and $x-1$ , inclusive, and move the token from cell $x$ to cell $x - y$ .
- Floored division: you choose an integer $z$ between $2$ and $x$ , inclusive, and move the token from cell $x$ to cell $\lfloor \frac{x}{z} \rfloor$ ( $x$ divided by $z$ rounded down).

Find the number of ways to move the token from cell $n$ to cell $1$ using one or more shifts, and print it modulo $m$ . Note that if there are several ways to move the token from one cell to another in one shift, all these ways are considered distinct (check example explanation for a better understanding).

The only line contains two integers $n$ and $m$ ( $2 \le n \le 4 \cdot 10^6$ ; $10^8 < m < 10^9$ ; $m$ is a prime number) — the length of the strip and the modulo.

Print the number of ways to move the token from cell $n$ to cell $1$ , modulo $m$ .

In the first test, there are three ways to move the token from cell $3$ to cell $1$ in one shift: using subtraction of $y = 2$ , or using division by $z = 2$ or $z = 3$ .

There are also two ways to move the token from cell $3$ to cell $1$ via cell $2$ : first subtract $y = 1$ , and then either subtract $y = 1$ again or divide by $z = 2$ .

Therefore, there are five ways in total.