زوج ما


  • محدودیت زمان: ۱ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

میلاد و پارسا که از رسیدن به مرحله‌ی نهایی کدکاپ ۳ جا ماندند، تصمیم به ترک دنیای کدزنی گرفتند و می‌خواهند تا آخر عمر با هم بازی کنند. میلاد از بازی‌هایی که شانس در آن‌ها دخیل است خسته‌ شده‌است.

دفعه آخری که میلاد و پارسا تخته نرد بازی کردند، پارسا مجموع تاس ۲۳۰ داشت و میلاد مجموع تاس ۱۵۰. میلاد به این باور رسیده‌است که نمی‌تواند در یک بازی که شانس در آن دخیل است پارسا را شکست دهد زیرا پارسا یک آدم خرشانس است.

میلاد می‌داند تنها زمینه‌ای که او از پارسا بهتر است، زبان C++C++ است، به همین دلیل پارسا را مجبور می‌کند که با او pairpair بازی کند.

بازی pairpair به این صورت است که ابتدا میلاد تعدادی کلمه pairpair یا intint پشت هم می‌نویسد که می‌توان بین آن‌ها طوری علامت گذاشت که pairpair ای قابل قبول برای C++C++ شود. (یعنی علامت های , و ‍‍< و ‍> که در میان این کلمات است را نمی‌گذارد.)

پس از آن بین کلمات pairpair و intint، به تعداد kk کلمه، pairpair یا intint دیگر اضافه می‌کند.

حال میلاد با گفتن عدد kk به پارسا از او می‌خواهد که تعداد راه‌هایی که او می‌تواند kk کلمه حذف کند به طوری که کلمات باقی‌مانده یک تعریف متغیر قابل قبول برای C++C++ باشد را به او بگوید.

از آنجایی که ممکن است این عدد خیلی بزرگ باشد پارسا باید باقیمانده آن به 109+710^9 + 7 را به میلاد بگوید.

از‌ آنجایی که پارسا سواد کافی در C++C++ ندارد از شما خواسته تا جواب میلاد را بدهید.

یک pairpair قابل قبول یک جفت به صورت pair<T1,T2> pair < T_1 , T_2 > است که در آن T1T_1 و T2T_2یا intint است یا یک pairpair قابل قبول.

با تعریف فوق مثال‌های زیر تعریف متغیر‌هایی قابل قبول می‌باشد:

pair < int , int >
pair < pair < int , int > , pair < int , int > >
pair < int , pair < pair < int , int > , int > >
Plain text

و مثال‌های زیر تعریف متغیرهایی غیر قابل قبول:

pair < int , int , int >
pair < pair < int , int > >
pair < int , pair >
Plain text

دقت کنید که حالتی وجود دارد که می‌توان طوری kk کلمه را حذف کرد به طوری که کلمات باقی‌مانده قابل قبول باشد.

ورودی🔗

در خط اول ابتدا عدد nn که تعداد کلمات رشته پس از تغییر است و سپس عدد kk به شما داده می‌شود.

در خط بعدی nn کلمه به شما داده می‌شود که هر کدام از کلمات یا pair است یا int.

4k+3n100 000 4 \le k + 3 \le n \le 100\ 000 1k10 1 \le k \le 10

خروجی🔗

باقیمانده تعداد راه‌های ممکن به 109+710^9 + 7 را در یک خط چاپ کنید.

مثال🔗

ورودی نمونه🔗

12 1
pair int pair pair int int pair pair int int int int
Plain text

خروجی نمونه🔗

7
Plain text
ارسال پاسخ برای این سؤال
در حال حاضر شما دسترسی ندارید.