• # For Solution

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 Up the Strip solution codeforces

The only line contains two integers nn and mm (2n41062≤n≤4⋅106108<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 solution codeforces

Copy
5

input

Copy
5 998244353

output

Copy
25

input

Copy
42 998244353

output

Copy
793019428

input

Copy
787788 100000007

output

Copy
94810539

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.