- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
میلاد و پارسا که از رسیدن به مرحلهی نهایی کدکاپ ۳ جا ماندند، تصمیم به ترک دنیای کدزنی گرفتند و میخواهند تا آخر عمر با هم بازی کنند. میلاد از بازیهایی که شانس در آنها دخیل است خسته شدهاست.
دفعه آخری که میلاد و پارسا تخته نرد بازی کردند، پارسا مجموع تاس ۲۳۰ داشت و میلاد مجموع تاس ۱۵۰. میلاد به این باور رسیدهاست که نمیتواند در یک بازی که شانس در آن دخیل است پارسا را شکست دهد زیرا پارسا یک آدم خرشانس است.
میلاد میداند تنها زمینهای که او از پارسا بهتر است، زبان \(C++\) است، به همین دلیل پارسا را مجبور میکند که با او \(pair\) بازی کند.
بازی \(pair\) به این صورت است که ابتدا میلاد تعدادی کلمه \(pair\) یا \(int\) پشت هم مینویسد که میتوان بین آنها طوری علامت گذاشت که \(pair\) ای قابل قبول برای \(C++\) شود. (یعنی علامت های , و < و > که در میان این کلمات است را نمیگذارد.)
پس از آن بین کلمات \(pair\) و \(int\)، به تعداد \(k\) کلمه، \(pair\) یا \(int\) دیگر اضافه میکند.
حال میلاد با گفتن عدد \(k\) به پارسا از او میخواهد که تعداد راههایی که او میتواند \(k\) کلمه حذف کند به طوری که کلمات باقیمانده یک تعریف متغیر قابل قبول برای \(C++\) باشد را به او بگوید.
از آنجایی که ممکن است این عدد خیلی بزرگ باشد پارسا باید باقیمانده آن به \(10^9 + 7\) را به میلاد بگوید.
از آنجایی که پارسا سواد کافی در \(C++\) ندارد از شما خواسته تا جواب میلاد را بدهید.
یک \(pair\) قابل قبول یک جفت به صورت \[ pair < T_1 , T_2 > \] است که در آن \(T_1\) و \(T_2\)یا \(int\) است یا یک \(pair\) قابل قبول.
با تعریف فوق مثالهای زیر تعریف متغیرهایی قابل قبول میباشد:
pair < int , int >
pair < pair < int , int > , pair < int , int > >
pair < int , pair < pair < int , int > , int > >
و مثالهای زیر تعریف متغیرهایی غیر قابل قبول:
pair < int , int , int >
pair < pair < int , int > >
pair < int , pair >
دقت کنید که حالتی وجود دارد که میتوان طوری \(k\) کلمه را حذف کرد به طوری که کلمات باقیمانده قابل قبول باشد.
ورودی
در خط اول ابتدا عدد \(n\) که تعداد کلمات رشته پس از تغییر است و سپس عدد \(k\) به شما داده میشود.
در خط بعدی \(n\) کلمه به شما داده میشود که هر کدام از کلمات یا pair است یا int.
\[ 4 \le k + 3 \le n \le 100\ 000 \] \[ 1 \le k \le 10\]
خروجی
باقیمانده تعداد راههای ممکن به \(10^9 + 7\) را در یک خط چاپ کنید.
مثال
ورودی نمونه
12 1
pair int pair pair int int pair pair int int int int
خروجی نمونه
7