+ محدودیت زمان: ۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- **دوره ۱۰۲۸ ایا** می‌خواستند از سطح دانش آموزانی که در آزمون های شاز در سال ۱۳۹۷ شرکت می‌کردند مطلع شوند. اما چون **دوره ۲۸ ایا** جزییات کامل رنکینگ‌ها را منتشر نکرده بودند، **دوره ۱۰۲۸ ایا** مجبور شدند تا رمز سرورها را به‌دست آورده و با استفاده از آن به رنکینگ‌های کامل دست یافته و سطح دانش‌آموزان را ارزیابی کنند. رمز سرورهای شاز در آن زمان یک جایگشت طولانی بود. **دوره ۲۸ ایا** که در تمام امور کارهایشان را گروهی انجام می‌دادند، انتخاب رمز را نیز مستثنی نکرده بودند. در زمان **دوره ۲۸ ایا**، $m$ نفر در دست‌اندرکاران شاز وجود داشتند ($8$ نفر اصلی و $m-8$ نفر دست‌های پشت پرده!) نفر $i$ ام از این افراد معتقد بود که اگر الگوی رمز مانند جایگشت $i$ ام باشد، رمز بسیار سخت است. عملیات چیدن تعدادی عدد متمایز مثل $a_k$...$a_1$ طبق جایگشت $p_k$...$p_1$ به اینصورت تعریف می‌شود که ترتیب اعداد آرایه $a$ را طوری تغییر می‌دهیم که به ازای هر دو اندیس متمایز $ 1 \leq i,j \leq k$ داشته باشیم: $a_i<a_j$ برقرار است اگر و فقط اگر $p_i<p_j$ برقرار باشد. مثلا اگر بخواهیم اعداد $\{8,7,4,11\}$ را طبق جایگشت $\{4,2,3,1\}$ بچینیم به $\{11,7,8,4\}$ تبدیل می‌شود‌. **دوره ۲۸ ایا** طول رمز را برحسب اهمیت آن، $n$ انتخاب می‌کردند. سپس در هر مرحله یکی از افراد تعدادی عدد از اعداد باقی‌مانده (اعداد مجموعه $1$ تا $n$ که تا حالا کسی آنها را در رمز استفاده نکرده است) انتخاب می‌کرد و آن ها را طبق جایگشت خودش می‌چید‌ و سپس آن را به **انتهای** رمز به دست آمده تا‌کنون اضافه می‌کرد. همچنین یک نفر ممکن است چند بار از جایگشتش استفاده کرده و رمز را گسترش دهد. حال **دوره ۱۰۲۸ ایا** حدس‌هایی راجع به رمز سرورهای شاز زده‌اند. اما آن ها می خواهند ببینند حدسشان چقدر محتمل است. برای همین از شما می‌خواهند بپرسند که رمز مذکور به چند طریق توسط **دوره ۲۸ ایا** قابل ساخت است. # ورودی خط اول ورودی عدد $n$ و$m$ داده می‌شود. در خط بعد جایگشت $p$ داده می‌شود که نشان دهنده رمز شاز است. سپس در $m$ خط بعدی جایگشت ها به این‌صورت داده می‌شود. در ابتدا عدد $k_i$ و سپس یک جایگشت $k_i$ تایی ورودی داده می‌شود. $$1 \le n, m , k_i \le 100\ 000$$ تضمین می‌شود که مجموع $k_i$ ها از $100\ 000$ بیشتر نمی‌شود. توجه کنید که ممکن است دو نفر الگوی جایگشتی مشابهی داشته باشند! # خروجی خروجی تنها شامل یک عدد است که تعداد راه‌های مختلف تولید رمز $p$ در پیمانه $10^9+7$ می‌باشد (دو روش تولید رمز متفاوت‌اند اگر تعداد بار‌هایی که رمز گسترش داده شده در آن دو روش متفاوت باشد یا اینکه این تعداد مساوی باشد اما در مرحله‌ای مثل $i$‌ **دو جایگشت متفاوت** برای گسترش رمز استفاده شده باشند). برای فهم بهتر ورودی نمونه ۳ را ببینید. # مثال ## ورودی نمونه ۱ ``` 5 2 5 3 2 4 1 4 4 1 3 2 1 1 ``` ## خروجی نمونه ۱ ``` 1 ``` در اینجا نمی توان از نقشه اول استفاده کرد و تنها حالت ممکن ۵ بار استفاده از نقشه دوم است. ## ورودی نمونه ۲ ``` 10 2 1 2 3 4 5 6 7 8 9 10 1 1 2 1 2 ``` ## خروجی نمونه ۲ ``` 89 ``` ## ورودی نمونه ۳ ``` 5 4 5 3 4 1 2 2 1 2 2 1 2 2 2 1 3 3 1 2 ``` ## خروجی نمونه ۳ ``` 2 ``` ## ورودی نمونه ۴ ``` 3 2 1 2 3 3 1 2 3 3 1 2 3 ``` ## خروجی نمونه ۴ ``` 1 ```