[Solution] Up the Strip solution codeforces

Up the Strip solution codeforces


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 (2n41062≤n≤4⋅106108<m<109108<m<109mm is a prime number) — the length of the strip and the modulo.

Output Up the Strip solution codeforces

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

Examples Up the Strip solution codeforces
input Up the Strip solution codeforces

Copy Up the Strip solution codeforces
3 998244353
output

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.

 

Solution: Click here

Up the Strip solution codeforcessolution codeforcescodeforces solutioncodeforces freshersonline

Leave a Comment