Description:
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).
Input Format:
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.
Output Format:
Print the number of ways to move the token from cell $$$n$$$ to cell $$$1$$$, modulo $$$m$$$.
Note:
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.