Problem Description

Little H is a child who loves sports. One day, he wants to make a running plan for himself. Little H plans to run $n$ meters in total. In the $i$-th minute ($i \geq 1$), he will run $x_i$ meters ($x_i$ is a positive integer), but the total duration is not fixed.

As the running time increases, Little H will get more and more tired, so his plan must satisfy that for any $i$ ($i > 1$), $x_i \leq x_{i-1}$.

Now Little H wants to know how many different plans satisfy the conditions. Two plans are different if and only if the total duration is different, or there exists an $i$ such that $x_i$ is different in the two plans.

Since the final answer may be very large, you only need to output the result modulo $p$.

Input Format

The input contains only one line with two integers, representing the total meters $n$ and the modulus $p$.

Output Format

Output one line with one integer, representing the answer modulo $p$.

4 44

5

66 666666

323522

66666 66666666

45183149

Hint

Explanation of Sample Input/Output 1

The five different plans are: $\{1,1,1,1\}$, $\{2,1,1\}$, $\{3,1\}$, $\{2,2\}$, $\{4\}$.

Constraints

This problem has $10$ test points. The information for each test point is shown in the table below.

For all test points, it is guaranteed that $1 \leq n \leq 10^5$, $1 \leq p < 2^{30}$.

Translated by ChatGPT 5