問題文

binapくんは人形遊びが好きです。いつも人形たちを円卓に座らせてお茶会を再現しているのですが、何通りの座らせ方があるのかがふと気になりました。

binapくんは $N$ 種類の人形を持っており、 $i$ 種類目の人形は $A_i$ 体あります。 円卓は $K$ 体の人形を等間隔で座らせることができます。また空席があってはなりません。

何通りの座らせ方があるか求めてあげてください。答えはとても大きな値になる場合がありますので素数 $998244353$ で割った余りを出力してください。

円卓を平面内でどのように回転させても座っている人形の種類を全て一致させることができないとき、またそのときに限り座らせ方が異なるとします。

制約

• $1 \leq N \leq 3\times10^5$

• $2 \leq K \leq 1300$

• $1 \leq A_i \leq 998244352(1\leq i \leq N)$

• $K \leq \sum_{i=1}^N A_i$

• 入力は全て整数

入力

$N$ $K$
$A_1$ $A_2$ $\cdots$ $A_N$

出力

座らせ方の総数を $998244353$ で割った余りを出力してください。

サンプル

3 3
2 1 1

4

3 6
3 4 1

32

5 4
4 4 3 2 1

128

14 14
1 1 1 1 1 1 1 1 1 1 1 1 1 1

237554682