सीमावर्ती 3
Problem
आज मोक्सी अच्छे मूड में है, इसलिए वह अपने बार में संगीत में विविधता लाना चाहती है।
ज्यूकबॉक्स एन गानों को स्टोर करता है, और उनमें से प्रत्येक को दो मापदंडों द्वारा चित्रित किया जाता है: ti और gi, जहां t_i — गाने की अवधि मिनटों में (1 ≤ ti ≤ 15), gi — इसकी शैली (1 ≤ gi ≤ 3)।
Moxxi एक ऐसी प्लेलिस्ट बनाना चाहता है जिसकी कुल अवधि ठीक T मिनट हो। ज्यूकबॉक्स कभी भी गानों को बाधित नहीं करता है और हमेशा उन्हें शुरू से अंत तक बजाता है। इस प्रकार, यदि वह i-वां गाना बजाना शुरू करता है, तो वह उस पर ठीक ti मिनट खर्च करेगा। Moxxi को भी यह पसंद नहीं है जब एक ही शैली के दो गाने एक पंक्ति में बजाए जाते हैं या जब गाने दोहराए जाते हैं।
Moxxi को गाने के विभिन्न अनुक्रमों की संख्या (उनका क्रम मायने रखता है) की संख्या की गणना करने में मदद करें, ठीक T की कुल अवधि के साथ, जैसे कि उनमें एक ही शैली के दो लगातार गाने नहीं हैं और प्लेलिस्ट में सभी गाने अलग-अलग हैं।
इनपुट:
इनपुट की पहली पंक्ति में दो पूर्णांक n और T (1 ≤ n ≤ 15, 1 ≤ T ≤ 225) — ज्यूकबॉक्स में गानों की संख्या और आवश्यक कुल अवधि, क्रमशः।
अगली n पंक्तियों में गीतों का वर्णन है: i-th पंक्ति में दो पूर्णांक हैं ti और gi (1 ≤ ti &le ; 15, 1 ≤gi ≤ 3) — क्रमशः i-वें गीत और इसकी शैली की अवधि।
आउटपुट:
एक पूर्णांक प्रिंट करें — गाने के विभिन्न अनुक्रमों की संख्या, बिल्कुल टी की कुल अवधि के साथ, जैसे कि उनमें एक ही शैली के दो लगातार गाने नहीं होते हैं और प्लेलिस्ट में सभी गाने अलग-अलग होते हैं। चूँकि उत्तर बड़ा हो सकता है, इसे मॉडुलो 109 + 7 प्रिंट करें (अर्थात, संख्या को 109 + 7 से विभाजित करने पर शेषफल)।
उदाहरण:
<तालिका सीमा = "1" सेलपैडिंग = "1" सेलस्पेसिंग = "1" शैली = "चौड़ाई: 500 पीएक्स;">
<शरीर>
| इनपुट |
आउटपुट |
3 3
1 1
1 2
1 3
| 6 |
3 3
1 1
1 1
1 3
| 2 |
स्पष्टीकरण:
पहले उदाहरण में, Moxxi उपलब्ध गीतों को पुनर्व्यवस्थित करके 6 प्लेलिस्ट विकल्पों में से कोई भी बना सकता है: [1,2,3], [1,3,2], [2,1,3], [2,3,1 ], [ 3,1,2] और [3,2,1] (गाने के अंक दर्शाए गए हैं)।
दूसरे उदाहरण में, पहला और दूसरा गीत लगातार नहीं हो सकते (क्योंकि उनकी शैली समान है)। इस प्रकार, Moxxi 2 संभावित तरीकों में से एक में एक प्लेलिस्ट बना सकता है: [1,3,2] और [2,3,1] (गाने की संख्या इंगित की गई है)।