Module: العد العودي

Problem

اليوم Moxxi في مزاج جيد ، لذا فهي تريد تنويع الموسيقى في الحانة الخاصة بها.
يخزن الصندوق الموسيقي عددًا من الأغاني ، وتتميز كل منها بمعاملتين: t _i و g _i ، حيث t_i & mdash؛ مدة الأغنية بالدقائق (1 & le؛ t _i & le؛ 15)، g _i & mdash؛ نوعه (1 & le؛ g _i & le؛ 3).
يريد Moxxi إنشاء قائمة تشغيل بحيث تكون مدتها الإجمالية بالضبط T دقيقة. لا يقاطع الموسيقي أبدًا الأغاني بل يقوم دائمًا بتشغيلها من البداية إلى النهاية. وبالتالي ، إذا بدأ تشغيل أغنية i ، فسوف يقضي بالضبط t _i دقيقة عليها. لا يعجب Moxxi أيضًا عندما يتم تشغيل أغنيتين من نفس النوع على التوالي أو عند تكرار الأغاني.
ساعد Moxxi في حساب عدد التسلسلات المختلفة للأغاني (ترتيبها مهم) ، بإجمالي مدة T بالضبط ، بحيث لا توجد أغنيتان متتاليتان من نفس النوع في كل منهما وتكون جميع الأغاني في قائمة التشغيل مختلفة.

الإدخال:
يحتوي السطر الأول من الإدخال على عددين صحيحين n و T (1 & le؛ n & le؛ 15، 1 & le؛ T & le؛ 225) & [مدش]؛ عدد الأغاني في الموسيقي والمدة الإجمالية المطلوبة على التوالي.
تحتوي الأسطر n التالية على أوصاف للأغاني: يحتوي السطر الأول على رقمين صحيحين t _i و g _i (1 & le؛ t _i & le ؛ 15، 1 & le؛ g _i & le؛ 3) & [مدش]؛ مدة الأغنية i ونوعها على التوالي.

الإخراج:
طباعة عدد صحيح واحد و [مدش] ؛ عدد التسلسلات المختلفة للأغاني ، بإجمالي مدة T بالضبط ، بحيث لا تحتوي على أغنيتين متتاليتين من نفس النوع وجميع الأغاني في قائمة التشغيل مختلفة. نظرًا لأن الإجابة يمكن أن تكون كبيرة ، اطبعها modulo 10 ⁹ + 7 (أي الباقي عند قسمة الرقم على الرقم 10 ⁹ + 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 ] و [3،1،2] و [3،2،1] (يشار إلى أرقام الأغاني).

في المثال الثاني ، لا يمكن أن تكون الأغنيتان الأولى والثانية متتاليتين (لأن لهما نفس النوع). وبالتالي ، يمكن لـ Moxxi إنشاء قائمة تشغيل بإحدى طريقتين محتملتين: [1،3،2] و [2،3،1] (يشار إلى أرقام الأغاني).