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

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

دنباله‌ی $q_{i}$ را برابر با $$p_1 + (i-1) \times n, p_2 + (i-1) \times n , \cdots , p_n + (i-1) \times n$$

تعریف می‌کنیم، حال جایگشت $p^2$ برابر است با:‌

$$q_{p_1} , q_{p_2} , ... , q_{p_n}$$

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

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

با توجه به این‌که این مقدار ممکن است بزرگ باشد، باقی‌مانده‌ی آن را بر $10^9 + 7$ محاسبه کنید.

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

ورودی

سطر اول ورودی شامل دو عدد طبیعی $m$ و $n$ است.

در هر یک از $m$ سطر بعدی به ترتیب دو عدد $c_i$ و $l_i$ آمده است که به معنای وجود $c_i$ دور به طول $l_i$ در گراف‌جایگشت $p^2$ است.

تضمین می‌شود که اندازه‌ی تمامی دور‌هایی که در سطر‌های دوم تا $m+1$ آمده‌اند متمایز است.

تضمین می‌شود که $c_1l_1 + c_2l_2 + ... + c_ml_m = n^2$ و حداقل یک جایگشت با چنین ابرجایگشتی وجود دارد.

$$1\le n,m\le 200\ 000$$

$$1\leq l_i , c_i \leq n^{2}$$

خروجی

در ابتدای خروجی گراف‌جایگشت یکی از جایگشت‌های $p$ که $p^2$ جایگشت داده‌شده در ورودی باشد را به همان فرمت ورودی چاپ کنید. در اولین سطر عدد $m$ و در $m$ سطر بعدی در هر سطر دو عدد $c_i$ و $l_i$ را چاپ کنید که نشان می‌دهد گراف‌جایگشت $p$، به تعداد $c_i$ تا دور به طول $l_i$ دارد. دقت کنید که $c_1l_1 + c_2l_2 + ... + c_ml_m$ باید برابر $n$ باشد و دنباله‌ی $l_i$ها باید اکیداً صعودی باشد. در صورت وجود چندین جواب هر کدام از آن‌ها را می‌توانید چاپ کنید.

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

زیرمسئله‌ها

مثال

ورودی نمونه ۱

2 3
1 1
4 2

خروجی نمونه ۱

2
1 1
1 2
3

ورودی نمونه ۲

1 4
4 4

خروجی نمونه ۲

1
1 4
6

ورودی نمونه ۳

5 9
2 2
3 3
8 4
2 6
2 12

خروجی نمونه ۳

3
1 2
1 3
1 4
15120

(۲۴امین دوره‌ المپیاد کامپیوتر - آزمون ششم - ۱۳۹۳/۰۶/۱۷)