Module: شمارش بازگشتی

Problem

امروز Moxxi حال و هوای خوبی دارد، بنابراین او می خواهد موسیقی را در نوار خود متنوع کند.
جوک باکس n آهنگ را ذخیره می کند و هر کدام از آنها با دو پارامتر مشخص می شود: t_i و g_i، جایی که t_i — مدت آهنگ به دقیقه (1 ≤ t_i ≤ 15)، g_i — ژانر آن (1 ≤ g_i ≤ 3).
Moxxi می خواهد یک لیست پخش بسازد که کل مدت آن دقیقا T دقیقه باشد. جوک باکس هرگز آهنگ ها را قطع نمی کند و همیشه آنها را از ابتدا تا انتها پخش می کند. بنابراین، اگر او شروع به پخش آهنگ i-ام کند، دقیقاً t_i دقیقه را صرف آن خواهد کرد. Moxxi همچنین وقتی دو آهنگ از یک سبک پشت سر هم پخش می شود یا زمانی که آهنگ ها تکرار می شوند، دوست ندارد.
به Moxxi کمک کنید تا تعداد سکانس‌های مختلف آهنگ‌ها را بشمارد (ترتیب آنها مهم است)، با مدت زمان کل دقیقاً T، به طوری که هیچ دو آهنگ متوالی از یک سبک در آنها وجود نداشته باشد و همه آهنگ‌های موجود در لیست پخش متفاوت باشند.

ورودی:
خط اول ورودی شامل دو عدد صحیح n و T (1 ≤ n ≤ 15، 1 ≤ T ≤ 225) — تعداد آهنگ های موجود در جوک باکس و مدت زمان مورد نیاز به ترتیب.
n سطر بعدی حاوی توضیحاتی درباره آهنگ ها است: خط i-ام شامل دو عدد صحیح t_i و g_i (1 ≤ t_i &le است. ; 15، 1 ≤g_i ≤ 3) — مدت زمان آهنگ i ام و ژانر آن به ترتیب.

خروجی:
چاپ یک عدد صحیح — تعداد سکانس‌های مختلف آهنگ، با مدت زمان کلی دقیقاً T، به طوری که شامل دو آهنگ متوالی از یک سبک نیستند و همه آهنگ‌های موجود در لیست پخش متفاوت هستند. از آنجایی که پاسخ می تواند بزرگ باشد، آن را با مدول 10⁹ + 7 چاپ کنید (یعنی باقیمانده زمانی که عدد بر عدد 10 تقسیم می شود⁹ + 7).

مثال:
  <بدن>

ورودی	خروجی
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] (شماره آهنگ ها مشخص شده است).