题目还是简单一点好。

设 $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}$ 。