题目描述
Problem Description
Little H is a child who loves sports. One day, he wants to create a running plan for himself. He plans to run a total of \( n \) meters, where in the \( i \)-th minute (\( i \geq 1 \)), he plans to run \( x_i \) meters (\( x_i \) is a positive integer), but he hasn't decided on the total duration.
Since Little H gets more tired as the running time increases, his plan must satisfy the condition that for any \( i > 1 \), \( x_i \leq x_{i-1} \).
Now, Little H wants to know how many different valid plans there are. Please help him. Two plans are considered 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 find the result modulo \( p \).
Input Format
The input consists of a single line with two integers, representing the total meters \( n \) and the modulus \( p \).
Output Format
Output a single integer, representing the answer modulo \( p \).
Sample Input and Output
Sample Input #1
4 44
Sample Output #1
5
Sample Input #2
66 666666
Sample Output #2
323522
Sample Input #3
66666 66666666
Sample Output #3
45183149
Notes
Explanation of Sample Input and Output #1
The five different plans are: \(\{1,1,1,1\}\), \(\{2,1,1\}\), \(\{3,1\}\), \(\{2,2\}\), and \(\{4\}\).
Data Size and Constraints
This problem consists of 10 test cases, with the details of each test case as follows:
| Test Case Number | \( n \leq \) | Test Case Number | \( n \leq \) |
|---|---|---|---|
| 1 | 5 | 6 | \( 2 \times 10^3 \) |
| 2 | 10 | 7 | \( 5 \times 10^3 \) |
| 3 | 50 | 8 | \( 2 \times 10^4 \) |
| 4 | 100 | 9 | \( 5 \times 10^4 \) |
| 5 | 500 | 10 | \( 10^5 \) |
For all test cases, it is guaranteed that \( 1 \leq n \leq 10^5 \) and \( 1 \leq p < 2^{30} \).
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分