#P1561D1. Up the Strip (simplified version)

    ID: 527 远端评测题 6000ms 128MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>brute forcedata structuresdpmathnumber theory*1700

Up the Strip (simplified version)

Description

This version of the problem differs from the next one only in the constraint on nn.

Note that the memory limit in this problem is lower than in others.

You have a vertical strip with nn cells, numbered consecutively from 11 to nn from top to bottom.

You also have a token that is initially placed in cell nn. You will move the token up until it arrives at cell 11.

Let the token be in cell x>1x > 1 at some moment. One shift of the token can have either of the following kinds:

  • Subtraction: you choose an integer yy between 11 and x1x-1, inclusive, and move the token from cell xx to cell xyx - y.
  • Floored division: you choose an integer zz between 22 and xx, inclusive, and move the token from cell xx to cell xz\lfloor \frac{x}{z} \rfloor (xx divided by zz rounded down).

Find the number of ways to move the token from cell nn to cell 11 using one or more shifts, and print it modulo mm. 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 nn and mm (2n21052 \le n \le 2 \cdot 10^5; 108<m<10910^8 < m < 10^9; mm is a prime number) — the length of the strip and the modulo.

Print the number of ways to move the token from cell nn to cell 11, modulo mm.

Input

The only line contains two integers nn and mm (2n21052 \le n \le 2 \cdot 10^5; 108<m<10910^8 < m < 10^9; mm is a prime number) — the length of the strip and the modulo.

Output

Print the number of ways to move the token from cell nn to cell 11, modulo mm.

Samples

样例输入 1

3 998244353

样例输出 1

5

样例输入 2

5 998244353

样例输出 2

25

样例输入 3

42 998244353

样例输出 3

793019428

Note

In the first test, there are three ways to move the token from cell 33 to cell 11 in one shift: using subtraction of y=2y = 2, or using division by z=2z = 2 or z=3z = 3.

There are also two ways to move the token from cell 33 to cell 11 via cell 22: first subtract y=1y = 1, and then either subtract y=1y = 1 again or divide by z=2z = 2.

Therefore, there are five ways in total.