#P1561D1. Up the Strip (simplified version)

ID: 7245 Type: RemoteJudge 6000ms 128MiB 尝试: 2 已通过: 2 难度: 10 上传者: 标签>brute forcedpmathnumber theory

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.