题目描述

有从 $1$ 到 $K$ 编号的 $K$ 个箱子。最初，这些箱子都是空的。

すぬけ君拥有一些写有 $1$ 到 $N$ 之间整数的球。在这些球中，写有数字 $i$ 的球有 $a_i$ 个。写有相同数字的球彼此之间不区分个体（即视为相同的球）。

すぬけ君打算把他拥有的所有球都放进这 $K$ 个箱子中。
他希望做到以下要求：

对于每一个箱子，数字为 $1$ 的球必须占据过半数。

所谓“占据过半数”是指：

数字为 $1$ 的球的个数 严格大于 其他所有球的总数。

请计算，满足上述条件的放球方式有多少种。答案对 $998244353$ 取模。

两个放法被认为是不同的，当且仅当存在满足 $1\ \leq\ i\ \leq\ K,\ 1\ \leq\ j\ \leq\ N$ 的整数对 $(i,j)$ 时，第 $i$ 个箱子中写有数字 $j$ 的球的数量不同。

输入格式

$N$ $K$ $a_1$ $\cdots$ $a_N$

输出格式

输出满足条件的放球方式的总数，对 $998244353$ 取模。

样例 1

输入

2 2
3 1

输出

2

样例 2

输入

2 1
1 100

输出

0

样例 3

输入

20 100
1073813 90585 41323 52293 62633 28788 1925 56222 54989 2772 36456 64841 26551 92115 63191 3603 82120 94450 71667 9325

输出

313918676

说明/提示

数据范围

• 所有输入均为整数
• $1 \leq N \leq 10^5$
• $1 \leq K \leq 200$
• $1 \leq a_i < 998244353$