Background

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

Problem Description

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

Input Format

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

Output Format

Write output to standard output.

Output one integer on a single line, representing the answer modulo $998244353$.

3 60
8 243 250

2304

Hint

[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]

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