{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e\u003cspan class\u003d\"tex-font-style-bf\"\u003e\u003cspan class\u003d\"tex-font-style-it\"\u003eSự khác biệt duy nhất giữa phiên bản dễ và khó là các ràng buộc.\u003c/span\u003e\u003c/span\u003e\u003c/p\u003e\u003cp\u003ePolycarp thích nghe nhạc, vì vậy anh ấy không bao giờ rời khỏi máy phát, ngay cả khi trên đường về nhà từ trường đại học. Polycarp vượt qua khoảng cách từ trường đại học đến nhà trong đúng $$$T$$$ phút.\u003c/p\u003e\u003cp\u003eTrong máy phát, Polycarp lưu trữ $$$n$$$ bài hát, mỗi bài hát được đặc trưng bởi hai tham số: $$$t_i$$$ và $$$g_i$$$, trong đó $$$t_i$$$ là độ dài của bài hát tính bằng phút ($$$1 \\le t_i \\le 15$$$), $$$g_i$$$ là thể loại của nó ($$$1 \\le g_i \\le 3$$$).\u003c/p\u003e\u003cp\u003ePolycarp muốn tạo ra một danh sách phát sao cho anh ấy có thể nghe nhạc suốt thời gian trên đường từ trường đại học về nhà, và khi đến nhà, danh sách phát đã kết thúc. Polycarp không bao giờ ngắt quãng bài hát và luôn nghe chúng từ đầu đến cuối. Do đó, nếu anh ấy bắt đầu nghe bài hát thứ $$$i$$$, anh ấy sẽ dành đúng $$$t_i$$$ phút để nghe nó. Polycarp cũng không thích khi hai bài hát cùng thể loại phát liên tiếp (tức là liên tiếp/đối diện) hoặc khi các bài hát trong danh sách phát của anh ấy bị lặp lại.\u003c/p\u003e\u003cp\u003eGiúp Polycarp đếm số lượng các chuỗi bài hát khác nhau (thứ tự của chúng quan trọng), tổng thời gian chính xác là $$$T$$$, sao cho không có hai bài hát liên tiếp nào 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.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eDòng đầu tiên của đầu vào chứa hai số nguyên $$$n$$$ và $$$T$$$ ($$$1 \\le n \\le 15, 1 \\le T \\le 225$$$) — số lượng bài hát trong máy phát và tổng thời gian yêu cầu, tương ứng.\u003c/p\u003e\u003cp\u003eKế tiếp, $$$n$$$ dòng chứa mô tả các bài hát: dòng thứ $$$i$$$ chứa hai số nguyên $$$t_i$$$ và $$$g_i$$$ ($$$1 \\le t_i \\le 15, 1 \\le g_i \\le 3$$$) — độ dài của bài hát thứ $$$i$$$ và thể loại của nó, tương ứng.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eXuất ra một số nguyên — số lượng các chuỗi bài hát khác nhau, tổng độ dài chính xác là $$$T$$$, sao cho không có hai bài hát liên tiếp nào 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ể rất lớn, hãy xuất nó theo modulo $$$10^9 + 7$$$ (tức là, phần dư khi chia số lượng cho $$$10^9 + 7$$$).\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3 3\n1 1\n1 2\n1 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e6\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3 3\n1 1\n1 1\n1 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4 10\n5 3\n2 1\n3 2\n5 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e10\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eTrong ví dụ đầu tiên, Polycarp có thể tạo bất kỳ danh sách phát nào trong số $$$6$$$ khả năng 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]$$$ (chỉ số của các bài hát được cung cấp).\u003c/p\u003e\u003cp\u003eTrong ví dụ thứ hai, bài hát đầu tiên và thứ hai không thể đi liền nhau (vì chúng có cùng thể loại). Do đó, Polycarp có thể tạo một danh sách phát theo một trong $$$2$$$ cách khả thi: $$$[1, 3, 2]$$$ và $$$[2, 3, 1]$$$ (chỉ số của các bài hát được cung cấp).\u003c/p\u003e\u003cp\u003eTrong ví dụ thứ ba, Polycarp có thể tạo các danh sách phát sau: $$$[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]$$$ và $$$[4, 3, 2]$$$ (chỉ số của các bài hát được cung cấp).\u003c/p\u003e"}}]}