题目描述

$1$ から $K$ の番号がついた $K$ 個の箱があります。はじめ、箱は全て空です。

すぬけ君は $1$ 以上 $N$ 以下の整数が書かれたボールをいくつか持っています。 すぬけ君が持っているボールのうち、$i$ が書かれたものは $a_i$ 個あります。 同じ整数が書かれたボール同士は区別できません。

すぬけ君は持っている全てのボールを箱にしまうことにしました。 すぬけ君はどの箱についても $1$ と書かれたボールが過半数を占めるようにしたいです。 過半数を占めるとは、$1$ と書かれたボールの個数がそれ以外のボールの個数より多いことを意味します。

そのようなしまい方の個数を $998244353$ で割ったあまりを求めてください。

$2$ つのしまい方が異なるとは、$1\ \leq\ i\ \leq\ K,\ 1\ \leq\ j\ \leq\ N$ を満たす整数の組 $(i,j)$ であって、箱 $i$ に入っている $j$ が書かれたボールの個数が異なるようなものが存在することをいいます。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

どの箱も $1$ と書かれたボールが過半数を占めるようなしまい方の個数を $998244353$ で割ったあまりを出力せよ。

题目大意

你有 $N$ 种角色，我们用一个在 $1$ 至 $N$ 之间的整数去区分他们，已知种类为 $i$ 的角色有 $a_i$ 个。现在，你为了刷圣遗物，你需要打 $K$ 个副本，很显然每个副本你都需要派遣出一些角色去战斗。已知种类为 $1$ 的角色为你的主要输出角色，其它的都是辅助，如果在一个副本中种类为 $1$ 的角色的数量小于种类为非 $1$ 的角色数量之和，那么这些辅助角色的加成会出现浪费。问你在不浪费任何一个辅助角色的加成的情况下，有多少种方式派遣这 $N$ 个角色刷完 $K$ 个副本。

2 2
3 1

2

2 1
1 100

0

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$

Sample Explanation 1

- $1$ と書かれたボールが過半数を占めるようなしまい方は $2$ 通りあります。 - 例えば $1$ と書かれたボールを箱 $1$ に $2$ 個、箱 $2$ に $1$ 個入れ、$2$ と書かれたボールを箱 $1$ に $1$ 個入れたとき条件を満たします。

Sample Explanation 2

- 条件を満たすようなしまい方が存在しないこともあります。

Sample Explanation 3

- $998244353$ で割ったあまりを求めるのを忘れずに。