Divide-and-Conquer on a tree is a powerful approach to solving tree problems.
Imagine a tree, , with vertices. Let's remove some vertex from tree , splitting into zero or more connected components, , with vertices . We can prove that there is a vertex, , such that the size of each formed components is at most .
The Divide-and-Conquer approach can be described as follows:
- Initially, there is a tree, , with vertices.
- Find vertex such that, if is removed from the tree, the size of each formed component after removing is at most .
- Remove from tree .
- Perform this approach recursively for each of the connected components.
We can prove that if we find such a vertex in linear time (e.g., using DFS), the entire approach works in . Of course, sometimes there are several such vertices that we can choose on some step, we can take and remove any of them. However, right now we are interested in trees such that at each step there is a unique vertex that we can choose.
Given , count the number of tree 's such that the Divide-and-Conquer approach works determinately on them. As this number can be quite large, your answer must be modulo .
Input Format
A single line of two space-separated positive integers describing the respective values of (the number of vertices in tree ) and (the modulo value).
Constraints
- is a prime number.
Subtasks
- for of the maximum score.
- for of the maximum score.
Output Format
Print a single integer denoting the number of tree 's such that vertex is unique at each step when applying the Divide-and-Conquer approach, modulo .
Sample Input 0
1 103
Sample Output 0
1
Explanation 0
For , there is only one way to build a tree so we print the value of as our answer.
Sample Input 1
2 103
Sample Output 1
0
Explanation 1
For , there is only one way to build a tree:
This tree is not valid because we can choose to remove either node or node in the first step. Thus, we print as no valid tree exists.
Sample Input 2
3 103
Sample Output 2
3
Explanation 2
For , there are valid trees depicted in the diagram below (the unique vertex removed in the first step is shown in red):
Thus, we print the value of as our answer.
Sample Input 3
4 103
Sample Output 3
4
Explanation 3
For , there are valid trees depicted in the diagram below (the unique vertex removed in the first step is shown in red):
The figure below shows an invalid tree with :
This tree is not valid because we can choose to remove node or node in the first step. Because we had four valid trees, we print the value of as our answer.