Description

在樱花盛开的四月，Muxii 望着满天飘落的樱花，向身旁的 ZZH 问道：

“究竟有多少朵樱花在这个四月飘落？”

ZZH 答道：“樱花飘落的朵数 $s$ 与时间 $t$ 有如下关系：

$$s=\prod_{x=1}^t\prod_{y|x}\frac{y^{d(y)}}{\prod_{z|y}(z+1)^2}$$

其中 $d(y)$ 表示 $y$ 的约数个数。”

但作为一个文科生萌新，Muxii 显然无法清楚地知道具体的数目，因此他只好继续向 ZZH 询问这个问题的答案。

由于数量可能很大，所以你只需要替 ZZH 告诉 Muxii 他所需要的答案对 $p$ 取模的结果就好了。

Input Format

两个正整数 $t$ 和 $p$，分别表示 Muxii 询问的时间、模数。

Output Format

输出一个正整数 $s$，表示樱花飘落的朵数。答案对 $p$ 取模。

4 998244353

648735108

10 1000000007

872041698

Hint

「样例 1 说明」

代入计算可得答案为 $\frac1{2073600}$，由于 $2073600$ 在模 $998244353$ 意义下的逆元为 $648735108$，故最终答案为 $1×648735108\bmod998244353 = 648735108$。

「数据范围与约定」

数据保证答案的最简表示中分母不含 $p$ 和 $p$ 的倍数。

对于所有数据，保证 $1\leq t\leq 2.5×10^9$，$9.9×10^8<p<1.1×10^9$ 且 $p$ 为质数。 |子任务编号|$t≤$|分值| |:-:|:-:|:-:| |$1$|$10^3$|$5$| |$2$|$10^4$|$5$| |$3$|$2×10^5$|$10$| |$4$|$2×10^6$|$20$| |$5$|$10^7$|$20$| |$6$|$10^8$|$20$| |$7$|$2.5×10^9$|$20$|

注：本题采用捆绑测试，即必须通过单个子任务的所有测试点才可获得该子任务的分数。