Spanning Tree Value Sum

You are given a graph with s nodes that is pre‐divided into n connected components due to the existence of s − n edges. The i-th connected component contains a_i nodes (and note that s = a₁ + a₂ + ... + a_n although these values are provided only for description purposes).

Now, you must add exactly n − 1 extra edges between these components (by connecting any vertex from one component to any vertex in another) so that the resulting graph becomes a tree spanning all s nodes. When a particular scheme of adding the edges is chosen, let the number of new edges incident to the i-th component be d_i (i.e. its degree in the tree connecting the components). The value of the resulting tree T is defined as follows:

$$\mathrm{val}(T) = \Bigl(\prod_{i=1}^{n} d_i^m\Bigr) \Bigl(\sum_{i=1}^{n} d_i^m\Bigr), $$

where m is a given non‐negative integer.

Your task is to compute the sum of \(\mathrm{val}(T)\) over all possible spanning trees (formed by connecting the n components with n−1 extra edges) modulo 998244353.

Input Note: The values a_i are provided in the input, though they do not affect the tree value computation. In other words, the answer depends solely on the numbers n and m.

inputFormat

The input consists of two lines.

• The first line contains two integers n and m (n ≥ 2), where n is the number of connected components and m is the exponent used in the definition of the tree value.
• The second line contains n positive integers: a₁, a₂, ..., a_n. These denote the number of nodes in each component. (Note that these values are only for context.)

outputFormat

Output a single integer—the sum of the values of all possible spanning trees formed by connecting the n components (using exactly n−1 extra edges), taken modulo 998244353.

sample

2 1
1 1

2

</p>