H. Jellyfish Sequence
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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$$$.

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$$$.

Examples
Input
4 9
Output
108
Input
1234 9876
Output
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.