Maximizing Tree Coverage Distance

You are given n trees by the roadside. Each tree has a positive integer height denoted by \(p_1, p_2, \dots, p_n\). The width of a tree is defined as the number of positive divisors of its height. The distance that a set of trees can cover is defined as the product of their widths.

You also have \(w\) units of magical fertilizer. You can perform several rounds of fertilization. In each round, if you have \(F\) units of fertilizer, you may choose any positive integer \(k\) satisfying \(k\) divides \(F\) (i.e. \(k\) is a positive divisor of \(F\)). Then you choose any one tree (different rounds may choose different trees) and multiply its height by \(k\). Simultaneously, the remaining fertilizer is updated to \(F/k\). You may perform as many fertilization rounds as you wish (using all or some of the fertilizer), but note that the product of all chosen \(k\) values in the rounds will equal the original \(w\) if you use all fertilizer.

The final height of each tree will be \(p_i\) multiplied by the product of all \(k\) values applied to that tree. Hence, if you denote by \(m_i\) the total multiplier for tree \(i\) (with \(m_i = 1\) if no fertilizer is applied), the overall coverage distance becomes:

[ D = \prod_{i=1}^{n} d(p_i \times m_i), ]

where \(d(x)\) denotes the number of positive divisors of \(x\). Using the fact that if \(x = \prod_{j} p_j^{a_j}\) then \(d(x) = \prod_{j} (a_j+1)\), note that fertilizing a tree effectively increases some prime exponents in its factorization. You are allowed to distribute the fertilizer units arbitrarily among the trees as long as the product of the multipliers equals \(w\).

Your task is to maximize \(D\) by choosing an optimal distribution of the fertilizer among the trees, and output the maximum possible \(D\) modulo \(998244353\).

Input Format: The first line contains two integers \(n\) and \(w\). The second line contains \(n\) positive integers \(p_1, p_2, \dots, p_n\).

Output Format: Output one integer, the maximum distance \(D\) modulo \(998244353\).

inputFormat

The first line contains two integers \(n\) and \(w\) separated by a space.

The second line contains \(n\) integers: \(p_1, p_2, \dots, p_n\), representing the heights of the trees.

outputFormat

Output one integer: the maximum distance the trees can cover, modulo \(998244353\).

sample

3 12
4 9 10

216