G2. Плейлист для Поликарпа (усложнённая версия)
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Единственное отличие этой версии от упрощённой — это ограничения.

Поликарп очень любит слушать музыку, поэтому он никогда не расстается с плеером, даже по пути из университета домой. Поликарп преодолевает расстояние от университета до дома ровно за $$$T$$$ минут.

В плеере у Поликарпа хранится $$$n$$$ песен, причем каждая из них характеризуется двумя параметрами: $$$t_i$$$ и $$$g_i$$$, где $$$t_i$$$ — длительность песни в минутах ($$$1 \le t_i \le 50$$$), $$$g_i$$$ — её жанр ($$$1 \le g_i \le 3$$$).

Поликарп хочет составить такой плейлист, чтобы всё время в пути от университета до дома, он мог слушать музыку и в момент прибытия домой плейлист кончился. Поликарп никогда не прерывает песни и всегда слушает их от начала и до конца. Таким образом, если он начал слушать $$$i$$$-ю песню, то на её прослушивание он потратит ровно $$$t_i$$$ минут. Также Поликарп не любит, когда подряд играют две песни одинакового жанра или когда песни в его плейлисте повторяются.

Помогите Поликарпу посчитать количество различных последовательностей песен (их порядок имеет значение), суммарной длительностью ровно $$$T$$$, таких, что в них нет двух подряд идущих песен одинакового жанра и все песни в плейлисте различны.

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

В первой строке входных данных записаны два целых числа $$$n$$$ и $$$T$$$ ($$$1 \le n \le 50, 1 \le T \le 2500$$$) — количество песен в плеере и требуемая суммарная длительность, соответственно.

Далее в $$$n$$$ строках записаны описания песен: $$$i$$$-я строка содержит два целых числа $$$t_i$$$ и $$$g_i$$$ ($$$1 \le t_i \le 50, 1 \le g_i \le 3$$$) — длительность $$$i$$$-й песни и её жанр, соответственно.

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

Выведите одно целое число — количество различных последовательностей песен, суммарной длительностью ровно $$$T$$$, таких, что в них нет двух подряд идущих песен одинакового жанра и все песни в плейлисте различны. Так как ответ может быть большим, выводите его по модулю $$$10^9 + 7$$$ (то есть остаток при делении количества на число $$$10^9 + 7$$$).

Примеры
Входные данные
3 3
1 1
1 2
1 3
Выходные данные
6
Входные данные
3 3
1 1
1 1
1 3
Выходные данные
2
Входные данные
4 10
5 3
2 1
3 2
5 1
Выходные данные
10
Примечание

В первом примере Поликарп может составить любой из $$$6$$$-ти вариантов плейлист перестановкой имеющихся песен: $$$[1, 2, 3]$$$, $$$[1, 3, 2]$$$, $$$[2, 1, 3]$$$, $$$[2, 3, 1]$$$, $$$[3, 1, 2]$$$ и $$$[3, 2, 1]$$$ (указаны номера песен).

Во втором примере первая и вторая песни не могут идти подряд (так как имеют одинаковый жанр). Таким образом, Поликарп может составить плейлист одним из $$$2$$$-х возможных способов: $$$[1, 3, 2]$$$ и $$$[2, 3, 1]$$$ (указаны номера песен).

В третьем примере Поликарп может составить следующие плейлисты: $$$[1, 2, 3]$$$, $$$[1, 3, 2]$$$, $$$[2, 1, 3]$$$, $$$[2, 3, 1]$$$, $$$[3, 1, 2]$$$, $$$[3, 2, 1]$$$, $$$[1, 4]$$$, $$$[4, 1]$$$, $$$[2, 3, 4]$$$ и $$$[4, 3, 2]$$$ (указаны номера песен).