P9836 Planting Trees

Little Rf does not really like planting flowers, but he likes planting trees.

There are $n$ trees by the roadside. The **height** of each tree is a positive integer, denoted as $p_1, p_2 \dots p_n$. Define the **width** of a tree as the number of positive divisors of its height. The distance these trees can cover is the product of their widths. You want to invite your friends to enjoy the shade, but you find that the distance these trees can cover is not large enough. So you buy a total of $w$ units of magic fertilizer. You may fertilize multiple times. Each time, you can use $k$ units of fertilizer (**$k$ must be a positive divisor of the current amount of fertilizer**), multiply the height of any one tree by $k$, and at the same time your remaining fertilizer amount will be divided by $k$. The tree chosen for each fertilization can be arbitrary, and the chosen trees do not need to be the same across operations. You need to maximize the distance that these trees can cover, and output this maximum distance. Take the answer modulo $998244353$.

Read input from standard input. The first line contains two positive integers $n$ and $w$. The second line contains $n$ positive integers $p_1, p_2 \dots p_n$.

Write output to standard output. Output one integer on a single line, representing the answer modulo $998244353$.

**[Sample 1 Explanation]** + First fertilization: apply $15$ units of fertilizer to the first tree, making its height become $120$, with $4$ units of fertilizer remaining. + Second fertilization: apply $4$ units of fertilizer to the second tree, making its height become $972$, with $1$ unit of fertilizer remaining. + At this time, the widths of the three trees are $16, 18, 8$ respectively, and the distance they can cover is $2304$, which is the optimal solution. --- **[Sample 2]** See the attached files $\texttt{plant/plant2.in}$ and $\texttt{plant/plant2.ans}$. --- **[Sample 3]** See the attached files $\texttt{plant/plant3.in}$ and $\texttt{plant/plant3.ans}$. --- **[Constraints]** | Test Point ID | $n \leq$ | $p_i$ | $w$ | Points | | :-----------: | :------: | :---: | :---: | :----: | | $1 \sim 5$ | $10^4$ | $=1$ | $=1$ | $1$ | | $6 \sim 10$ | $10^4$ | $\leq 10^4$ | $=1$ | $3$ | | $11 \sim 15$ | $1$ | $\leq 10^4$ | $\leq 10^4$ | $3$ | | $16 \sim 20$ | $5$ | $\leq 10^4$ | $\leq 10^4$ | $6$ | | $21 \sim 25$ | $10^4$ | $\leq 10^4$ | $\leq 10^4$ | $7$ | For $100\%$ of the testdata, it is guaranteed that $1 \leq n \leq 10^4$, $1 \leq p_i \leq 10^4$, and $1 \leq w \leq 10^4$. Translated by ChatGPT 5