题目还是简单一点好。
设 $g(x)$ 为 $x$ 的可重质因子数目，例如 $g\left(2^{3}\right)=g(2 \times 3 \times 5)=g\left(2 \times 3^{2}\right)=3, g(1)=0$ 。设 $f(x)=2^{g(x)}$ ，你需要求出 $\sum_{i=1}^{n} f(i)$ ，对输入的质数 $p$ 取模。
Input
一行两个整数 $n, p$ 。
Output
一行，$\left(\sum_{i=1}^{n} f(i)\right) \bmod p$ 。
Examples
Input
10 998244353
Output
33
Input
10000000 998244353
Output
746263855
Input
100000000000000 998244353
Output
954677937
Notes
对于所有数据， $1 \leq n \leq 10^{14}, 0.9 \times 10^{9} < p < 10^{9}, p$ 为质数。
- 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}$ 。