+ محدودیت زمان: ۳ ثانیه + محدودیت حافظه: ۵۱۲ مگابایت ---------- ابواسحاق که از شر دشمنانش جان سالم به در برده بود، تصمیم گرفت جشنی عظیم برگزار کند. آقا تیزی که قبل از شروع جشن به آنجا رسیده بود، تصمیم گرفت در آماده کردن تزئینات به ابواسحاق کمک کند. برای همین، ابواسحاق $k$ ریسه به آقا تیزی داد. هر ریسه شامل $n$ لامپ رنگی متوالی است. رنگ لامپ‌ها در یک ریسه، جایگشتی از اعداد ۱ تا $n$ است؛ سپس از او خواست تا از ابتدا و انتهای هر ریسه تعدادی لامپ حذف کند (ممکن است هیچ لامپی حذف نشود، امّا همهٔ لامپ‌ها حذف نمی‌شوند)، با این شرط که در ریسه‌های جدید به ازای هر دو ریسه مانند $a$ و $b$، هر رنگ که در ریسهٔ $a$ آمده در ریسهٔ $b$ نیز آمده باشد. آقا تیزی که می‌خواهد زیباترین تزئینات را انجام دهد، از شما می‌خواهد که تعداد روش‌های مختلف انجام این کار را به او بگویید تا بهترین را انتخاب کند (دو روش متفاوت هستند، اگر در ریسه‌ای لامپی حذف شود که در دیگری حذف نشده باشد). # ورودی در خط اول ورودی دو عدد $n$ و $k$ آمده است که به ترتیب تعداد لامپ‌های هر ریسه و تعداد ریسه‌ها را مشخص می‌کند. در هر یک از $k$ خط بعدی، $n$ عدد داده شده است که عدد $j$ اُم در سطر $i$ اُم برابر با $a_{i,j}$ است. ($a_{i,j}$ نشان دهندهٔ رنگ لامپ $j$ اُم در ریسهٔ $i$ اُم است) $$2 \le k \le 1\ 000\ 000$$ $$1 \le n \times k \le 1\ 000\ 000$$ $$1 \le a_{i,j} \le n$$ **تضمین می‌شود رنگ لامپ‌های موجود در یک ریسه جایگشتی از اعداد $1$ تا $n$ است.** # خروجی در تنها خط خروجی تعداد حالات خواسته شده را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 3 2 1 3 2 2 1 3 ``` ## خروجی نمونه ۱ ``` 5 ``` <details> <summary>توضیحات مثال</summary> ۵ حالت ممکن به این ترتیب است: + از ریسه اول دو لامپ آخر و از ریسه دوم لامپ اول و آخر حذف شود + از ریسه اول دو لامپ اول و از ریسه دوم دو لامپ آخر حذف شود. + از ریسه اول لامپ اول و آخر و از ریسه دوم دو لامپ اول حذف شود. + از ریسه اول لامپ آخر و از ریسه دوم لامپ اول حذف شود. + از هیچ یک از ریسه‌ها لامپی حذف نشود. </details> ## ورودی نمونه ۲ ``` 3 3 1 2 3 2 1 3 3 2 1 ``` ## خروجی نمونه ۲ ``` 5 ``` <details> <summary>توضیحات مثال</summary> ۵ حالت ممکن به این ترتیب است: + پس از عملیات حذف، ریسه‌های ۱ و ۲ و ۳ به ترتیب به شکل $[1]$ و $[1]$ و $[1]$ درمی‌آیند. + پس از عملیات حذف، ریسه‌های ۱ و ۲ و ۳ به ترتیب به شکل $[2]$ و $[2]$ و $[2]$ درمی‌آیند. + پس از عملیات حذف، ریسه‌های ۱ و ۲ و ۳ به ترتیب به شکل $[3]$ و $[3]$ و $[3]$ درمی‌آیند. + پس از عملیات حذف، ریسه‌های ۱ و ۲ و ۳ به ترتیب به شکل $[1,2]$ و $[2,1]$ و $[2,1]$ درمی‌آیند. + پس از عملیات حذف، ریسه‌های ۱ و ۲ و ۳ به ترتیب به شکل $[1,2,3]$ و $[2,1,3]$ و $[3,2,1]$ درمی‌آیند. </details>

حل سؤال در بانک سؤالات