codeforces#P1561D1. Up the Strip (simplified version)
Up the Strip (simplified version)
Description
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$.
Input
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.
Output
Print the number of ways to move the token from cell $n$ to cell $1$, modulo $m$.
Samples
3 998244353
5
5 998244353
25
42 998244353
793019428
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.