Маленький W решил отправиться в выпускное путешествие и приехал в город T. В городе T есть $n$ достопримечательностей. Он хочет выехать из отеля, посетить каждую достопримечательность ровно один раз и вернуться в отель.

Однако маленький W не хочет слишком сильно утомляться. В частности, при перемещении от одной достопримечательности к другой он испытывает утомление. У каждой достопримечательности есть целочисленный вес $v_i$. Если он переходит от $i$-й достопримечательности к $j$-й, его утомление составляет $v_i \times v_j$. Утомление всей поездки определяется как максимальное из значений утомления при всех перемещениях.

Маленький W не хочет слишком сильно утомляться, поэтому он хочет найти такой план путешествия, чтобы утомление всей поездки было меньше неотрицательного целого числа $w$. Он считает, что эта задача слишком проста для вас, поэтому хочет узнать, сколько всего существует различных планов путешествия, удовлетворяющих этому условию. Ответ нужно вывести по модулю $998244353$.

Входные данные

В первой строке заданы два числа $n$ и $w$, обозначающие количество достопримечательностей и ограничение на утомление соответственно.

Во второй строке заданы $n$ целых чисел $v_i$, обозначающих веса каждой достопримечательности.

Выходные данные

Выведите одно целое число — ответ на задачу.

Примеры

Пример 1

Входные данные

3 3
1 2 3

Выходные данные

2

Пример 2

Входные данные

6 5
1 1 4 5 1 4

Выходные данные

144

Пример 3

Входные данные

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

Выходные данные

802901549

Подзадачи

Для всех данных $0 \le w, |v_i| \le 10^9$, $1 \le n \le 200000$.

• Подзадача 1 (10 баллов): $n \le 200$, $v_i \ge 0$
• Подзадача 2 (10 баллов): $n \le 2000$, $v_i \ge 0$
• Подзадача 3 (10 баллов): $n \le 50000$, $v_i \ge 0$
• Подзадача 4 (10 баллов): $n \le 200000$, $v_i \ge 0$
• Подзадача 5 (10 баллов): $n \le 200$
• Подзадача 6 (10 баллов): $n \le 2000$
• Подзадача 7 (20 баллов): $n \le 50000$
• Подзадача 8 (20 баллов): $n \le 200000$