"Little Flower, because it's a flower."
Frank is fascinated by the beauty of numbers.
One day, Frank was watering flowers in his garden. Looking at the beautiful petals, he thought it would be wonderful if each flower could grow numbers.
So, he took out paper and pen and started sketching his ideal "number flower". An undirected connected graph is called a "number flower" if and only if it satisfies the following three conditions:
- If the graph contains $$$n$$$ nodes, these nodes should be labeled from $$$1$$$ to $$$n$$$.
- The graph contains exactly $$$n-1$$$ edges. No node has a degree greater than $$$2$$$ except for node $$$1$$$.
- Nodes directly connected to node $$$1$$$ are called key nodes. All key nodes have pairwise coprime labels. For each non-key node (except node $$$1$$$), its label is a multiple of the nearest key node's label, and the labels along the simple path from the non-key node to its nearest key node are monotonically decreasing.
Given an integer $$$n$$$, how many different "number flowers" with $$$n$$$ nodes are there? Two graphs $$$G_1$$$ and $$$G_2$$$ are considered the same if and only if for any edge $$$(u, v)$$$ in $$$G_1$$$, a corresponding edge $$$(u, v)$$$ exists in $$$G_2$$$.
Since the answer is huge, you only need to output it modulo a prime number $$$p$$$.
There is only one test case in each test file.
The first line contains two positive integers $$$n$$$ and $$$p$$$ ($$$1 \leq n \leq 10^{10}$$$, $$$10^8 \lt p \lt 10^9$$$).
It is guaranteed that $$$p$$$ is a prime number.
Output a single integer, which is the number of different "number flowers" modulo $$$p$$$.
5 998244353
1
10 998244353
4
10000000000 998244353
889033323
Example $$$1$$$ Illustration For the first example, there is only one "number flower", which is shown in the figure.
