+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۵۱۲ مگابایت ___ بعد از ۳ بار افتادن درس «معادلات دیفرانسیل» و ۲ بار حذف «فیزیک ۲» محمدرضا تونست مدرک کارشناسی اش رو بگیره. یک روز که محمدرضا رفت مدرک کارشناسی اش رو بگیره و بعدش بره برای آزمون کارشناسی ارشد ثبت نام کنه تو دانشکده یکی از اساتید رو دید: استاد: تو مگه درس طراحی الگوریتم رو پاس کردی؟ محمدرضا: بله استاد. استاد: حتما اشتباهی شده. برو این سوال رو حل کن ببینم. اگر نتونی حل کنی مدرک بی مدرک. محمدرضا: :| یه کمکی به محمدرضا بکنین که بتونه مدرکش رو بگیره. سوال استاد: «$n$ تا عملیات داریم که هر کدوم از یکی از عملیات های ضرب و جمع و تفریق و یک عدد تشکیل شدند. مثلا ۴+ یا ۲× یا ۳-. می خوایم با این عملیات ها با شروع از عدد ۱ عدد $k$ رو بسازیم. به چند روش می تونیم این کار رو بکنیم به شرطی که در طی عملیات هامون عدد بیشتر از 2*k و کمتر از 1 تولید نشود و امکان استفاده از هر عملیات به هر تعداد باری که می خوایم باشه؟ چون این عدد ممکنه خیلی بزرگ بشه باقی مونده این عدد به ۱۰۰۰۰۰۰۰۰۷ رو حساب کن.» # ورودی در سطر اول ورودی دو عدد $n$ و $k$ به ترتیب آمده اند. در $n$ سطر بعدی در هر سطر یک عملیات و یک عدد($a_i$) اومده. عملیات و عدد با یک فاصله از هم جدا شده اند $$ 0 \le n, k \le 5000 $$ $$ 0 \le a_i \le 5000 $$ # خروجی در تنها سطر خروجی تعداد راه های ساخت عدد $k$ با استفاده از این عملیات ها رو بنویسید. # مثال ## ورودی ۱ ``` 3 7 + 3 * 2 + 5 ``` ## خروجی ۱ ``` 3 ``` ### توضیح عدد ۶ را به روش های زیر می توان تولید کرد. دقت کنید که هر عملیات روی خروجی عملیات های گذشته انجام می شود(که این موضوع با پرانتز گذاری در روش های زیر مشخص شده است). ``` ((1*2)+5) ((1+3)+3) (((1*2)*2)+3) ``` ## ورودی ۲ ``` 4 6 + 3 * 2 - 7 + 5 ``` ### خروجی ۲ ``` infinite ``` ### توضیح عدد ۶ را با نامتناهی روش می توان ساخت: (برای وضوح بیشتر پرانتز ها را حذف می کنم اما روش اعمال عملیات ها مشابه قبل است. مثلا در خط اول ابتدا 2*1 محاسبه می شود و سپس 2(حاصل عملیات قبلی) در عملیات 2× مورد استفاده قرار می گیرد و سپس 4 در عملیات 2× مورد استفاده قرار می گیرد و ...) ``` 1*2*2*2-7+5 1*2*2+2-7*2*2*2-7+5 1*2*2+2-7*2*2*2-7*2*2*2-7+5 ... ```