• For Solution

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⌊xz⌋ (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).

Input

The only line contains two integers nn and mm (2n21052≤n≤2⋅105108<m<109108<m<109mm 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.

Examples
input

Copy
3 998244353

output Up the Strip (simplified version) solution codeforces

Copy
5

input

Copy
5 998244353

output Up the Strip (simplified version) solution codeforces

Copy
25

input Up the Strip (simplified version) solution codeforces

Copy
42 998244353

output

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