سوال ۳

اگر $p_1, p_2, \cdots , p_n$ جایگشتی از اعداد $1$ تا $n‌$ باشد، جایگشت $p^2$ که آن را ابرجایگشت $p$ می‌نامیم، یک جایگشت $n^2$ تایی است که به صورت زیر تعریف می‌شود:‌

دنباله‌ی $q_i$ را برابر با $p_1 + (i − 1) * n, p_2 + (i − 1) * n, \cdots , p_n + (i − 1) * n$ تعریف می‌کنیم، حال جایگشت $p^2$ برابر است با:‌ $q_{p_1}, q_{p_2},\cdots , q_{p_n} $.

برای مثال ابرجایگشت $2 \ 3 \ 1$ برابر است با $5 \ 6 \ 4 \ 8 \ 9 \ 7 \ 2 \ 3 \ 1$.

برنامه‌ای بنویسید که اندازه‌ی دور‌های گراف‌جایگشت یک ابر‌جایگشت را به عنوان ورودی بگیرد و تعداد جایگشت‌های $n$ تایی مانند $p$ که گراف‌جایگشت $p^2$ به این شکل است را در خروجی چاپ کند. با توجه به این‌که این مقدار ممکن است بزرگ باشد، باقی‌مانده‌ی آن را بر $10^9 + 7$ محاسبه کنید.

با تشکر از آقای مهندس و خانم دکتر!

• سطر اول ورودی شامل دو عدد طبیعی $m$ و $n$ است.
• در هر یک از $m$ سطر بعدی به ترتیب دو عدد $c_i$ و $l_i$ آمده است که به معنای وجود $c_i$ دور به طول $l_i$ در گراف‌جایگشت $p^2$ است.
• تضمین می‌شود که اندازه‌ی تمامی دور‌هایی که در سطر‌های دوم تا $m + 1$ آمده‌اند متمایز است.
• تضمین می‌شود که $c_1/1 + c_2/2 + . . .  + c_m/m = n^2$ و حداقل یک جایگشت با چنین ابرجایگشتی وجود دارد.
• $1 \leq n, m \leq 2 * 10^5$
• $1 \leq l_i, c_i \leq n^2$

در ابتدای خروجی گراف‌جایگشت یکی از جایگشت‌های $p$ که $p^2$ جایگشت داده‌شده در ورودی باشد را به همان فرمت ورودی چاپ کنید. در اولین سطر عدد $m$ و در $m$ سطر بعدی در هر سطر دو عدد $c_i$ و $l_i$ را چاپ کنید که نشان می‌دهد گراف‌جایگشت $p$، به تعداد $c_i$ تا دور به طول $l_i$ دارد. دقت کنید که $c_1/1 + c_2/2 + \cdots+ c_m/m$ باید برابر $n$ باشد و هیچ دو $l_i$ای با یک‌دیگر برابر نباشند. در صورت وجود چندین جواب هر کدام از آن‌ها را می‌توانید چاپ کنید.

در سطر آخر خروجی با‌قی‌مانده‌ی تعداد جایگشت‌هایی که گراف ابر جایگشت‌ آن‌ها مطابق ورودی است را بر $10^9 + 7$ چاپ کنید.

نمره‌دهی این سوال به این شکل است که اگر جایگشت ارائه شده اشتباه باشد نمره‌ای به شما تعلق نمی‌گیرد، در صورتی که جایگشت ارائه شده درست باشد ولی تعداد جایگشت‌های با این شرایط را اشتباه چاپ کرده‌ باشید، نیمی از نمره به شما تعلق می‌گیرد و تنها در صورتی نمره‌ی کامل می‌گیرید که هم جایگشت ارائه شده و هم تعداد جایگشت‌ها درست باشد. (به ازای هر زیرمساله)

• زیرمسئله اول (۱۰ نمره): $n \leq 8$
• زیرمسئله دوم (۱۰ نمره): $m = 1$
• زیرمسئله سوم (۴۰ نمره): $n, m \leq 2000$
• زیرمسئله چهارم (۴۰ نمره): بدون محدودیت اضافی

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

• سوال قبل