Up the Strip solution codeforces
Note that the memory limit in this problem is lower than in others.
You have a vertical strip withcells, numbered consecutively from to from top to bottom.
You also have a token that is initially placed in cell. You will move the token up until it arrives at cell .
Let the token be in cellat some moment. One shift of the token can have either of the following kinds:
- Subtraction: you choose an integer between and , inclusive, and move the token from cell to cell .
- Floored division: you choose an integer between and , inclusive, and move the token from cell to cell ( divided by rounded down).
Find the number of ways to move the token from cell distinct (check example explanation for a better understanding).to cell using one or more shifts, and print it modulo . Note that if there are several ways to move the token from one cell to another in one shift, all these ways are considered
The only line contains two integersand ( ; ; is a prime number) — the length of the strip and the modulo.
Print the number of ways to move the token from cellto cell , modulo .
In the first test, there are three ways to move the token from cellto cell in one shift: using subtraction of , or using division by or .
There are also two ways to move the token from cellto cell via cell : first subtract , and then either subtract again or divide by .
Therefore, there are five ways in total.