#GYM104763H. Jellyfish Sequence
Jellyfish Sequence
本题没有可用的提交语言。
Description
For a nice weekend vacation, you decided to take a trip to the aquarium. There, you saw $n$ jellyfish, and you noticed a specific pattern in the number of tentacles they had. The first jellyfish you saw had $a_1$ tentacles. Surprisingly, the $i$th jellyfish had $a_i = (a_1 \cdot a_2 \cdots a_{i - 2} \cdot a_{i - 1}) \cdot p_i$ tentacles, where $p_i$ is the smallest prime that does not divide $a_1 \cdot a_2 \cdots a_{i - 2} \cdot a_{i - 1}$!
You also notice that a jellyfish's popularity is defined by how many sizes you can divide the number of tentacles by. More formally, if a jellyfish has $m$ tentacles, then their popularity score is the number of divisors of $m$. You want to find out, what is the maximum popularity score of all the jellyfish that you saw? Because the answer may be large, output it mod $998244353$.
The first line contains two integers $n$ and $a_1$ ($1 \leq n, a_1 \leq 10^5$) — the number of jellyfish and the number of tentacles the first jellyfish has.
Output one integer — the maximum number of divisors any jellyfish has, mod $998244353$.
Input
The first line contains two integers $n$ and $a_1$ ($1 \leq n, a_1 \leq 10^5$) — the number of jellyfish and the number of tentacles the first jellyfish has.
Output
Output one integer — the maximum number of divisors any jellyfish has, mod $998244353$.
4 9
1234 9876
108
882891106
Note
In the first sample:
- $a_1 = 9$
- The smallest prime not a factor of $a_1$ is 2, so $a_2 = (9) \cdot 2 = 18$.
- The smallest prime not a factor of $a_1 \cdot a_2$ is 5, so $a_3 = (9 \cdot 18) \cdot 5 = 810$.
- The smallest prime not a factor of $a_1 \cdot a_2 \cdot a_3$ is 7, so $a_4 = (9 \cdot 18 \cdot 810) \cdot 7 = 918,540$.
Each of these have $3$, $6$, $20$, and $108$ factors respectively, so the answer is $108$.
Note that you want the mod of the maximum, not the maximum after taking the mod of the number of tentacles each jellyfish has.