#P1561D1. Up the Strip (simplified version)
Up the Strip (simplified version)
Description
This version of the problem differs from the next one only in the constraint on .
Note that the memory limit in this problem is lower than in others.
You have a vertical strip with cells, 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 cell at 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 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 distinct (check example explanation for a better understanding).
The only line contains two integers and (; ; is a prime number) — the length of the strip and the modulo.
Print the number of ways to move the token from cell to cell , modulo .
Input
The only line contains two integers and (; ; is a prime number) — the length of the strip and the modulo.
Output
Print the number of ways to move the token from cell to cell , modulo .
Samples
Note
In the first test, there are three ways to move the token from cell to cell in one shift: using subtraction of , or using division by or .
There are also two ways to move the token from cell to cell via cell : first subtract , and then either subtract again or divide by .
Therefore, there are five ways in total.