Problem
오늘 목시는 기분이 좋아서 그녀의 바에서 음악을 다양화하고 싶어합니다.
주크박스는 n개의 노래를 저장하고 각 노래는 t
i 및 g
i의 두 가지 매개변수로 특징지어집니다. 여기서 t_i — 노래 재생 시간(1 ≤ t
i ≤ 15), g
i — 장르(1 ≤ g
i ≤ 3).
Moxxi는 총 재생 시간이 정확히 T분인 재생 목록을 만들고자 합니다. 주크박스는 노래를 중단하지 않고 항상 처음부터 끝까지 재생합니다. 따라서 그가 i번째 노래를 재생하기 시작하면 정확히 t
i분을 그 노래에 사용할 것입니다. Moxxi도 같은 장르의 두 곡이 연속으로 재생되거나 노래가 반복되는 것을 좋아하지 않습니다.
Moxxi가 동일한 장르의 연속된 두 곡이 없고 재생 목록의 모든 곡이 서로 다르도록 총 재생 시간이 정확히 T인 곡의 서로 다른 시퀀스(순서가 중요함)의 수를 세도록 도와주세요.
입력:
입력의 첫 번째 줄에는 두 개의 정수 n과 T(1 < n < 15, 1 < T < 225)가 포함됩니다. 주크박스의 노래 수와 필요한 총 재생 시간.
다음 n행에는 노래에 대한 설명이 포함됩니다. i번째 행에는 두 개의 정수 t
i 및 g
i(1 ≤ t
i &le ;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 |
설명:
첫 번째 예에서 Moxxi는 [1,2,3], [1,3,2], [2,1,3], [2,3,1]의 사용 가능한 노래를 재정렬하여 6개의 재생 목록 옵션을 만들 수 있습니다. ], [ 3,1,2] 및 [3,2,1](곡 번호가 표시됨).
두 번째 예에서 첫 번째와 두 번째 노래는 연속될 수 없습니다(장르가 같기 때문). 따라서 Moxxi는 [1,3,2] 및 [2,3,1](노래 번호가 표시됨)의 두 가지 방법 중 하나로 재생 목록을 만들 수 있습니다.