Background

An easy problem, no background.

Problem Description

For a multiset $S$, define one operation on $S$ as follows:

• Let $\rm avg$ be the average of all elements in $S$, i.e. $\frac{\sum S}{|S|}$, where $\sum S$ is the sum of all elements in $S$, and $|S|$ is the number of elements in $S$ (duplicate elements are counted multiple times).
• Let $m=\min\limits_{x \in S}|x-\mathrm{avg}|$, i.e. the minimum value of the absolute difference between an element in $S$ and $\rm avg$.
• Choose an element $x$ from $S$ such that $|x-\mathrm{avg}|=m$. If multiple elements satisfy this, choose any one of them.
• Then delete one $x$ from $S$, and insert one $\rm avg$ into $S$.

For example, performing one operation on $\{2,4,1,4,6,1\}$ can yield $\{3,4,1,4,6,1\}$ or $\{2,4,1,3,6,1\}$. Note that a multiset is unordered.

Given positive integers $n,k$ and a multiset $A=\{a_1,a_2,\cdots,a_n\}$, compute how many different multisets may be obtained after performing $k$ operations on $A$. Output the result modulo $998244353$.

Input Format

The first line contains two positive integers $n,k$, separated by spaces.
The second line contains $n$ positive integers $a_1,a_2,\cdots,a_n$, separated by spaces.

Output Format

Output one non-negative integer in one line, denoting the number of different multisets that may be obtained modulo $998244353$.

6 1
2 4 1 4 6 1 

2

2 3
1 9 

8

Hint

Sample 1 Explanation

The following multisets may be obtained: $\{3,4,1,4,6,1\},\{2,4,1,3,6,1\}$.

Note that $\{2,3,1,4,6,1\}$ is the same as $\{2,4,1,3,6,1\}$.

Constraints

It is guaranteed that $1 \le n \le 5 \times 10^5,1 \le a_i,k \le 10^9$.

This problem uses bundled testdata.

Special conditions for subtasks are as follows:

Translated by ChatGPT 5