Description

In April, when sakura are in full bloom, Muxii looked at the sakura falling all over the sky and asked ZZH beside him:

"Exactly how many sakura petals fall in this April?"

ZZH answered: "The number of fallen sakura, $s$, and time $t$ satisfy the following relation:

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

where $d(y)$ denotes the number of divisors of $y$."

But as a liberal arts student beginner, Muxii obviously could not clearly know the exact value, so he had to keep asking ZZH for the answer to this question.

Since the value may be very large, you only need to tell Muxii the result of the answer modulo $p$ for ZZH.

Input Format

Two positive integers $t$ and $p$, representing the time asked by Muxii and the modulus, respectively.

Output Format

Output a positive integer $s$, representing the number of fallen sakura. Output the answer modulo $p$.

4 998244353

648735108

10 1000000007

872041698

Hint

"Sample 1 Explanation"

By direct substitution, the answer is $\frac1{2073600}$. Since the modular inverse of $2073600$ modulo $998244353$ is $648735108$, the final answer is $1×648735108\bmod998244353 = 648735108$.

"Constraints and Notes"

The testdata guarantees that in the fraction in lowest terms of the answer, the denominator does not contain $p$ or any multiple of $p$.

For all testdata, it is guaranteed that $1\leq t\leq 2.5×10^9$, $9.9×10^8<p<1.1×10^9$, and $p$ is a prime number. |Subtask ID|$t\leq$|Score| |:-:|:-:|:-:| |$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$|

Note: This problem uses bundled judging, meaning you must pass all test points of a subtask to receive the score for that subtask.

Translated by ChatGPT 5