Mały W postanowił wybrać się w podróż po ukończeniu studiów i przyjechał do miasta T. W mieście T znajduje się $n$ atrakcji turystycznych. Chce on wyruszyć z hotelu, odwiedzić każdą atrakcję dokładnie raz, a następnie wrócić do hotelu.

Mały W nie chce się jednak zbytnio przemęczyć. Mówiąc konkretnie, odczuwa on zmęczenie podczas przemieszczania się między dwiema atrakcjami. Każda atrakcja ma przypisaną liczbę całkowitą $v_i$. Jeśli przemieści się z atrakcji $i$ do atrakcji $j$, jego zmęczenie wynosi $v_i \times v_j$. Całkowite zmęczenie z podróży definiuje się jako maksymalną wartość zmęczenia odnotowaną podczas wszystkich przemieszczeń.

Mały W nie chce być zbyt zmęczony, dlatego chce znaleźć plan podróży, w którym całkowite zmęczenie jest mniejsze niż pewna nieujemna liczba całkowita $w$. Uważa on jednak, że to zadanie jest dla Ciebie zbyt proste, więc pyta, ile istnieje różnych planów podróży spełniających ten warunek. Wynik należy podać modulo $998244353$.

Wejście

W pierwszej linii znajdują się dwie liczby $n$ oraz $w$, oznaczające odpowiednio liczbę atrakcji oraz limit zmęczenia.

W drugiej linii znajduje się $n$ liczb całkowitych $v_i$, oznaczających wagi poszczególnych atrakcji.

Wyjście

W jednej linii wypisz jedną liczbę całkowitą oznaczającą wynik.

Przykład

Przykład 1

Wejście:

3 3
1 2 3

Wyjście:

2

Przykład 2

Wejście:

6 5
1 1 4 5 1 4

Wyjście:

144

Przykład 3

Wejście:

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

Wyjście:

802901549

Podzadania

Dla wszystkich danych wejściowych: $0 \le w, |v_i| \le 10^9$, $1 \le n \le 200000$.

• Podzadanie 1 (10 pkt): $n \le 200$, $v_i \ge 0$
• Podzadanie 2 (10 pkt): $n \le 2000$, $v_i \ge 0$
• Podzadanie 3 (10 pkt): $n \le 50000$, $v_i \ge 0$
• Podzadanie 4 (10 pkt): $n \le 200000$, $v_i \ge 0$
• Podzadanie 5 (10 pkt): $n \le 200$
• Podzadanie 6 (10 pkt): $n \le 2000$
• Podzadanie 7 (20 pkt): $n \le 50000$
• Podzadanie 8 (20 pkt): $n \le 200000$