CF1558B.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 \gt 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).

注意：本题的内存限制比其他题目更低。

你有一条垂直的格子带，共 $n$ 个格子，从上到下依次编号为 $1$ 到 $n$。

你还拥有一个初始位于第 $n$ 个格子的标记（token）。你需要将该标记向上移动，直至到达第 $1$ 个格子。

假设在某一时刻，标记位于第 $x$ 个格子，且 $x > 1$。一次移动操作有以下两种类型之一：

• 减法操作：你选择一个整数 $y$，满足 $1 \le y \le x-1$，并将标记从第 $x$ 个格子移动到第 $x - y$ 个格子；
• 向下取整除法操作：你选择一个整数 $z$，满足 $2 \le z \le x$，并将标记从第 $x$ 个格子移动到第 $\lfloor \frac{x}{z} \rfloor$ 个格子（即 $x$ 除以 $z$ 后向下取整）。

求出将标记从第 $n$ 个格子移动到第 $1$ 个格子所需的一次或多次移动操作的方案总数，并将结果对 $m$ 取模后输出。注意：若存在多种方式通过一次移动操作将标记从某格子移动至另一格子，则这些方式均被视为互不相同的方案（参见样例解释以获得更清晰的理解）。

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

唯一一行包含两个整数 $n$ 和 $m$（$2 \le n \le 4 \cdot 10^6$；$10^8 \lt m \lt 10^9$；$m$ 是一个质数）—— 分别表示条带的长度和取模数。

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

输出将棋子从第 $n$ 个格子移动到第 $1$ 个格子的方法数，对 $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.

在第一个测试中，有三种方式可以在一次移动中将棋子从第 $3$ 个格子移动到第 $1$ 个格子：使用减法（$y = 2$），或使用除法（$z = 2$ 或 $z = 3$）。

此外，还有两种方式可以通过第 $2$ 个格子将棋子从第 $3$ 个格子移动到第 $1$ 个格子：先减去 $y = 1$，然后再次减去 $y = 1$，或除以 $z = 2$。

因此，总共有五种方式。