Problem
Hôm nay tâm trạng Moxxi rất tốt nên cô ấy muốn đa dạng hóa âm nhạc trong quán bar của mình.
Máy hát tự động lưu trữ n bài hát và mỗi bài hát được đặc trưng bởi hai tham số: t
i và g
i, trong đó t_i — thời lượng bài hát tính bằng phút (1 ≤ t
i ≤ 15), g
i — thể loại của nó (1 ≤ g
i ≤ 3).
Moxxi muốn tạo một danh sách phát sao cho tổng thời lượng của danh sách đó chính xác là T phút. Máy hát tự động không bao giờ làm gián đoạn các bài hát và luôn phát chúng từ đầu đến cuối. Do đó, nếu anh ấy bắt đầu chơi bài hát thứ i, thì anh ấy sẽ dành đúng t
i phút cho bài hát đó. Moxxi cũng không thích khi hai bài hát cùng thể loại được phát liên tiếp hoặc khi các bài hát được lặp lại.
Giúp Moxxi đếm số chuỗi bài hát khác nhau (thứ tự quan trọng), với tổng thời lượng chính xác là T, sao cho không có hai bài hát liên tiếp cùng thể loại trong đó và tất cả các bài hát trong danh sách phát đều khác nhau.
Đầu vào:
Dòng đầu tiên chứa hai số nguyên n và T (1 ≤ n ≤ 15, 1 ≤ T ≤ 225) — tương ứng là số lượng bài hát trong máy hát tự động và tổng thời lượng yêu cầu.
n dòng tiếp theo chứa nội dung mô tả bài hát: dòng thứ i chứa 2 số nguyên t
i và g
i (1 ≤ t
i &le ; 15, 1 ≤g
i ≤ 3) — tương ứng là thời lượng của bài hát thứ i và thể loại của nó.
Đầu ra:
In một số nguyên duy nhất — số lượng các chuỗi bài hát khác nhau, với tổng thời lượng chính xác là T, sao cho chúng không chứa hai bài hát liên tiếp cùng thể loại và tất cả các bài hát trong danh sách phát đều khác nhau. Vì câu trả lời có thể lớn, hãy in nó theo modulo 10
9 + 7 (nghĩa là phần dư khi số đó chia cho số 10
9 + 7).
Ví dụ:
| Đầu vào |
Đầu ra |
3 3
1 1
1 2
1 3
| 6 |
3 3
1 1
1 1
1 3
| 2 |
Giải thích:
Trong ví dụ đầu tiên, Moxxi có thể tạo bất kỳ tùy chọn nào trong số 6 tùy chọn danh sách phát bằng cách sắp xếp lại các bài hát có sẵn: [1,2,3], [1,3,2], [2,1,3], [2,3,1 ], [ 3,1,2] và [3,2,1] (số bài hát được chỉ định).
Trong ví dụ thứ hai, bài hát đầu tiên và bài hát thứ hai không thể liên tiếp nhau (vì chúng có cùng thể loại). Do đó, Moxxi có thể tạo danh sách phát theo một trong 2 cách có thể: [1,3,2] và [2,3,1] (số bài hát được chỉ định).