It is better to keep problems simple.
Let $g(x)$ be the number of prime factors of $x$ counted with multiplicity. For example, $g\left(2^{3}\right)=g(2 \times 3 \times 5)=g\left(2 \times 3^{2}\right)=3$, and $g(1)=0$. Let $f(x)=2^{g(x)}$. You need to calculate $\sum_{i=1}^{n} f(i)$ modulo a given prime $p$.
Input
A single line containing two integers $n$ and $p$.
Output
A single line containing $\left(\sum_{i=1}^{n} f(i)\right) \bmod p$.
Examples
Input 1
10 998244353
Output 1
33
Input 2
10000000 998244353
Output 2
746263855
Input 3
100000000000000 998244353
Output 3
954677937
Subtasks
For all test cases, $1 \leq n \leq 10^{14}$, $0.9 \times 10^{9} < p < 10^{9}$, and $p$ is a prime number.
- Subtask 1 (10 pts): $n \leq 100$.
- Subtask 2 (10 pts): $n \leq 10^{7}$.
- Subtask 3 (20 pts): $n \leq 10^{10}$.
- Subtask 4 (20 pts): $n \leq 10^{12}$.
- Subtask 5 (20 pts): $n \leq 10^{13}$.
- Subtask 6 (20 pts): $n \leq 10^{14}$.