{"trustable":false,"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\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"MD","content":"Ngày thường, Tèo là một cậu nhóc hay đem ám khí đến với mọi người và không làm ngày của mọi người trở nên tươi đẹp hơn. Nhưng mấy ai biết (thực ra chả ai quan tâm) rằng về ban đêm, lúc cậu ở một mình, cậu là một đứa trẻ trầm tư và thích hòa mình vào thế giới của âm nhạc.\n\nÂm nhạc đã giúp cậu vượt qua những ngày tháng khó khăn nhất từ cái hồi cậu còn ở trại trẻ mồ côi (để đi từ thiện), hay cái thời cả gia đình nhà cậu bị nước lũ (ở công viên nước) cuốn trôi, hay cả thời cậu phiêu bạt vô gia cư ở ngoài vỉa hè nữa (thử thách làm ăn xin 24h của NTN). Vì vậy, cậu rất biết ơn đến nó. Hàng ngày, mỗi sáng, Tèo đến trường với một playlist khác nhau, nhưng playlist đó đều chỉ chứa một số trong **N** bài nhạc có trong máy mp3 của cậu.\n\nMỗi bài nhạc trong máy cậu đều có 2 thông số: **t(i)** và **g(i)**. **t(i)** là độ dài của bài nhạc theo đơn vị phút, và **g(i)** là thể loại nhạc của bài đó.\n\nTèo muốn một cái playlist dài đúng bằng thời gian cậu đi bộ từ nhà tới trường, tức là đúng **T** phút. Trong quãng thời gian đi bộ, cậu sẽ tập trung đi bộ để tích ám khí trong người, và cậu sẽ nghe nhạc không ngừng nghỉ dù chỉ 1 giây. Các bài hát trong list nhạc hôm đó của Tèo cũng sẽ được phát liên tiếp, không có giây nào ngắt quãng giữa các bài.\n\nHãy tính xem có bao nhiêu cách sắp xếp các bài trong list nhạc của Tèo sao cho:\n\n- Độ dài đúng **T** phút.\n- Không có bài nào được lặp lại.\n- Không có hai bài cùng thể loại đứng liền nhau."}},{"title":"Input","value":{"format":"MD","content":"Dòng đầu chứa hai số **N** và **T**. (**1 \u003c\u003d N \u003c\u003d 15**, **1 \u003c\u003d T \u003c\u003d 225**) - số bài hát trong máy Tèo và thời gian Tèo đi bộ từ nhà đến trường.\n\nTiếp theo, **N** dòng, dòng thứ **i** chứa **t_i** và **g_i** (**1 \u003c\u003d t_i \u003c\u003d 15**, **1 \u003c\u003d g_i \u003c\u003d 3**)."}},{"title":"Output","value":{"format":"MD","content":"In ra số cách có thể sắp xếp cho Tèo một playlist. Kết quả có thể sẽ lớn, nên hãy in nó ra modulo **1e9 + 7**."}},{"title":"Examples","value":{"format":"MD","content":"\u003cdiv class\u003d\"sample-test\"\u003e\n \u003cdiv class\u003d\"input\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Input 1\n \u003c/div\u003e\n \u003cpre\u003e3 3\n1 1\n1 2\n1 3\n\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"output\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Output 1\n \u003c/div\u003e\n \u003cpre\u003e6\n\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"input\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Input 2\n \u003c/div\u003e\n \u003cpre\u003e3 3\n1 1\n1 1\n1 3\n\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"output\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Output 2\n \u003c/div\u003e\n \u003cpre\u003e2\n\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"input\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Input 3\n \u003c/div\u003e\n \u003cpre\u003e4 10\n5 3\n2 1\n3 2\n5 1\n\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"output\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Output 3\n \u003c/div\u003e\n \u003cpre\u003e10\n\u003c/pre\u003e\n \u003c/div\u003e\n\u003c/div\u003e"}},{"title":"Note","value":{"format":"MD","content":"Ví dụ 1: [1,2,3] , [1,3,2], [2,1,3], [2,3,1], [3,1,2] and [3,2,1]\n\nVí dụ 3: [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] and [4,3,2]"}}]}