Up the Strip

题意翻译

### 题面描述 你有一张 $ 1 \times n $ 的纸带，由 $ n $ 个格子组成。初始有一个点在 $ n $ 号格子（即左数第 $ n $ 个）中。 假设现在这个点在 $ x\ (x > 1) $ 号格子，每次你可以对这个点进行如下操作中的一种： 1. 减法。选择一个 $ [1, x - 1] $ 中的正整数 $ y $，将点移动到 $ x - y $ 号格子中。 2. 除法。选择一个 $ [2, x] $ 中的正整数 $ z $，将点移动到 $ \lfloor \frac{x}{z} \rfloor $ 号格子中。 当点在 $ 1 $ 号格子中时无法移动，操作结束。 求将点从 $ n $ 号格子移到 $ 1 $ 号格子的方案数，答案对给定的模数取模。 两个方案不同当且仅当有一步选择的操作或选择的数不同。例如：$ x = 5 $ 时，选择操作 $ 1 $ 且 $ y = 4 $，或选择操作 $ 2 $ 且 $ z = 3\ 或\ 4\ 或\ 5 $ 时，点都将被移到 $ 1 $ 号格子，但这些都是不同的方案。 ### 输入格式 一行两个数，纸带长度 $ n $ 和模数 $ m $。 ### 输出格式 一行一个数，表示答案对 $ m $ 取模的结果。 ### 数据范围 $ 2 \leqslant n \leqslant 4 \cdot 10^6, 10^8 < m < 10^9, m $ 是质数。

题目描述

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 $ .

输入输出样例

输入样例 #1

3 998244353

输出样例 #1

5

输入样例 #2

5 998244353

输出样例 #2

25

输入样例 #3

42 998244353

输出样例 #3

793019428

输入样例 #4

787788 100000007

输出样例 #4

94810539

说明

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.