Up the Strip (simplified version)

题意翻译

给定一个数 $n$，每次可以对他进行一个操作，有两种操作： - $n \leftarrow n-t$，$t \in [1,n)$； - $n \leftarrow \lfloor\frac n t\rfloor$，$t \in (1,n]$。 求有多少种方案使得 $n$ 变为 $1$，答案对 $m$ 取模。 $2 \le n \le 2 \times 10^5$，$10^8<m<10^9$。

题目描述

This version of the problem differs from the next one only in the constraint on $ n $ . 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 2 \cdot 10^5 $ ; $ 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

说明

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.

题意翻译

给定一个数 $n$，每次可以对他进行一个操作，有两种操作： - $n \leftarrow n-t$，$t \in [1,n)$； - $n \leftarrow \lfloor\frac n t\rfloor$，$t \in (1,n]$。 求有多少种方案使得 $n$ 变为 $1$，答案对 $m$ 取模。 $2 \le n \le 2 \times 10^5$，$10^8<m<10^9$。