小 W は卒業旅行に出かけることにし、T 市を訪れました。T 市には $n$ 個の観光スポットがあり、彼はホテルを出発し、すべての観光スポットをちょうど一度ずつ経由してホテルに戻ることを計画しています。

しかし、小 W はあまり疲れたくありません。具体的には、ある観光スポットから別の観光スポットへ移動する際に疲労を感じます。各観光スポットには 整数 の重み $a_i$ が割り当てられており、観光スポット $i$ から観光スポット $j$ へ移動する場合、小 W の疲労度は $a_i \times a_j$ となります。旅全体の疲労度は、移動時の疲労度の最大値として定義されます。

小 W は疲れすぎないように、旅全体の疲労度が 非負整数 $w$ 未満となるような旅行計画を見つけたいと考えています。彼はこの問題があなたにとって簡単すぎると考え、条件を満たす旅行計画が全部で何通りあるかを $998244353$ で割った余りで求めるよう求めています。

入力形式

1 行目に 2 つの整数 $n, w$ が与えられ、それぞれ観光スポットの数と疲労度の制限を表します。

2 行目に $n$ 個の整数 $a_i$ が与えられ、それぞれ各観光スポットの重みを表します。

出力形式

答えを 1 行で出力してください。

入出力例

入力 1

3 3
1 2 3

出力 1

2

入力 2

6 5
1 1 4 5 1 4

出力 2

144

入力 3

16 20
-1 9 -9 9 -1 3 -9 2 -8 4 -1 4 0 8 5 3

出力 3

802901549

小課題

すべてのデータにおいて、$0 \le w, |a_i| \le 10^9$、$1 \le n \le 200000$ を満たします。

• subtask 1 (10 pts): $n \le 200$、$a_i \ge 0$
• subtask 2 (10 pts): $n \le 2000$、$a_i \ge 0$
• subtask 3 (10 pts): $n \le 50000$、$a_i \ge 0$
• subtask 4 (10 pts): $n \le 200000$、$a_i \ge 0$
• subtask 5 (10 pts): $n \le 200$
• subtask 6 (10 pts): $n \le 2000$
• subtask 7 (20 pts): $n \le 50000$
• subtask 8 (20 pts): $n \le 200000$