Сегодня у Мокси хорошее настроение, поэтому она хочет разнообразить музыку в своем баре.
В музыкальном автомате хранится n песен, причем каждая из них характеризуется двумя параметрами: t
i и g
i, где t_i — длительность песни в минутах (1 ≤ t
i ≤ 15), g
i — её жанр (1 ≤ g
i ≤ 3).
Мокси хочет составить такой плейлист, чтобы суммарная его длительность составляла ровно Т минут. Музыкальный автомат никогда не прерывает песни и всегда воспроизводит их от начала и до конца. Таким образом, если он начал воспроизводить i-ю песню, то на это он потратит ровно t
i минут. Также Мокси не любит, когда подряд играют две песни одинакового жанра или когда песни повторяются.
Помогите Мокси посчитать количество различных последовательностей песен (их порядок имеет значение), суммарной длительностью ровно T, таких, что в них нет двух подряд идущих песен одинакового жанра и все песни в плейлисте различны.
Входные данные:
В первой строке входных данных записаны два целых числа n и T (1 ≤ n ≤ 15, 1 ≤ T ≤ 225) — количество песен в музыкальном автомате и требуемая суммарная длительность, соответственно.
Далее в n строках записаны описания песен: i-я строка содержит два целых числа t
i и g
i (1 ≤ t
i ≤ 15, 1 ≤ g
i ≤ 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 |
Пояснения:
В первом примере Мокси может составить любой из 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] (указаны номера песен).