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

دوره ۱۰۲۸ ایا می‌خواستند از سطح دانش آموزانی که در آزمون های شاز در سال ۱۳۹۷ شرکت می‌کردند مطلع شوند. اما چون دوره ۲۸ ایا جزییات کامل رنکینگ‌ها را منتشر نکرده بودند، دوره ۱۰۲۸ ایا مجبور شدند تا رمز سرورها را به‌دست آورده و با استفاده از آن به رنکینگ‌های کامل دست یافته و سطح دانش‌آموزان را ارزیابی کنند. رمز سرورهای شاز در آن زمان یک جایگشت طولانی بود. دوره ۲۸ ایا که در تمام امور کارهایشان را گروهی انجام می‌دادند، انتخاب رمز را نیز مستثنی نکرده بودند. در زمان دوره ۲۸ ایا، $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