Единственное отличие этой версии от упрощённой — это ограничения.
Поликарп очень любит слушать музыку, поэтому он никогда не расстается с плеером, даже по пути из университета домой. Поликарп преодолевает расстояние от университета до дома ровно за \(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\), таких, что в них нет двух подряд идущих песен одинакового жанра и все песни в плейлисте различны.
Выходные данные
Выведите одно целое число — количество различных последовательностей песен, суммарной длительностью ровно \(T\), таких, что в них нет двух подряд идущих песен одинакового жанра и все песни в плейлисте различны. Так как ответ может быть большим, выводите его по модулю \(10^9 + 7\) (то есть остаток при делении количества на число \(10^9 + 7\)).
Примечание
В первом примере Поликарп может составить любой из \(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]\) (указаны номера песен).