نهایی


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

پس از برگزاری کلاس‌های دوره‌ی تابستانه‌ی المپیاد کامپیوتر، زمان برگزاری امتحانات نهایی عملی رسیده است.

در این دوره‌ی تابستانه nn دانش‌پژوه در حال دانش پژوهیدن بودند و بنابراین در امتحانات نهایی نیز nn دانش‌پژوه دانش خواهند پژوهید. در سالن برگزاری امتحانات نیز nn کامپیوتر برای آن‌ها آماده شده‌است که دور یک میز دایره‌ای قرار گرفته‌اند و به ترتیب ساعتگرد با اعداد 11 تا nn شماره‌گذاری شده‌اند.

امیرمحمّد که خیلی دوست داشت اثری از او در امتحانات نهایی هم موجود باشد، وظیفه‌ی خطیر مشخّص کردن جای نشستن دانش‌پژوهان در آزمون اوّل را برعهده گرفت. بنابراین به هر دانش‌پژوه یک عدد از 11 تا nn نسبت داد که شماره‌ی کامپیوتر او را مشخّص می‌کرد. به عبارت دیگر یک آرایه‌ی aa به طول nn مشخّص کرد که aia_i شماره‌ی کامپیوتر دانش‌پژوه iiام در حین آزمون را مشخّص می‌کرد.

امّا قضیه به همین سادگی‌ها نبود... به دلیل پاره‌ای از مشکلات فنّی، آرایه‌ی aa شامل تعدادی عضو تکراری بود! یعنی به برخی از دانش‌پژوهان کامپیوتر یکسانی نسبت داده شده بود. امیرمحمّد که پیش از شروع امتحان متوجّه این ماجرا شده بود، مشکل را با مجید در میان گذاشت.

مجید تصمیم گرفت روند نشستن دانش پژوهان در سالن به این شکل باشد که ابتدا آن‌ها پشت در سالن امتحان در یک صف بایستند؛ سپس به ترتیب از ابتدای صف وارد سالن امتحان شوند. هر گاه دانش‌پژوهی وارد سالن امتحان شد و دید که دانش‌پژوهی پشت کامپیوتر مورد نظرش نشسته است، سراغ کامپیوتر بعدی(در جهت ساعتگرد) برود. دانش‌پژوه باید این کار را تا زمانی ادامه دهد که به یک کامپیوتر خالی برسد و پای آن کامپیوتر بنشیند. به عبارت دیگر دانش‌پژوه iiام پشت اوّلین کامپیوتر بعد از aia_i(با احتساب خود aia_i) می‌نشیند که در زمان وارد شدن او به سالن دانش‌پژوه دیگری پشتش ننشسته باشد. پس از آن که هر دانش‌پژوه پشت کامپیوتری نشست، نفر بعدی صف وارد سالن می‌شود.

به این ترتیب دانش‌پژوهان بدون مشکل خاصی توانستند پای کامپیوترهایشان بنشینند و آزمون با خوبی و خوشی برگزار شود. در حین برگزاری آزمون مجید ماجرای پیش آمده را برای شایان تعریف کرد. شایان که به شدّت از کمبود سوال برای امتحانات عملی رنج می‌برد، تصمیم گرفت از این ماجرا هم سوالی طرح کند! شایان آرایه‌ی bb به طول nn را تعریف کرد: bib_i شماره کامپیوتری است که دانش‌آموز iiام پشت آن نشسته است. سوال شایان این بود که اگر ما آرایه‌ی aa و bb را داشته باشیم، دانش‌پژوهان به چند طریق می‌توانند پشت در سالن امتحان صفی تشکیل دهند که پس از آن که وارد سالن شدند، که دانش‌آموز iiام پشت کامپیوتر bib_i نشسته باشد.

شایان که باید به آماده‌سازی سوالات دیگری بپردازد، از شما می‌خواهد این سوال را برای او حل کنید!

ورودی🔗

در سطر اول ورودی عدد nn آمده‌است.
در iiامین سطر بعد، به ترتیب دو عدد aia_i و bib_i آمده‌است.
تضمین می‌شود که آرایه‌ی bb یک جایگشت است.

  • 1n1051 \le n \le 10^{5}
  • 1ai,bin1 \le a_i, b_i \le n

خروجی🔗

در تنها خط خروجی, باقی‌مانده‌ی تعداد ترتیب‌های معتبر را به پیمانه‌ی 109+710^9 + 7 خروجی دهید.

زیر مسئله ها🔗

زیرمسئله نمره محدودیت ها
۱ ۷ n10n \le 10
۲ ۸ حداکثر یک حالت مطلوب وجود دارد.
۳ ۲۵ 1in:biai0 or 1(modn)\forall_{1 \le i \le n} : {b_i - a_i \equiv {0 \ or \ 1} \pmod{n}}
۴ ۶۰ بدون محدودیت اضافی

مثال🔗

ورودی نمونه ۱🔗

3
2 2
3 3
2 1
Plain text

خروجی نمونه ۱🔗

2
Plain text

ورودی نمونه ۲🔗

13
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10
11 11
12 12
13 13
Plain text

خروجی نمونه ۲🔗

227020758
Plain text

ورودی نمونه ۳🔗

4
4 4
3 1
1 2
2 3
Plain text

خروجی نمونه ۳🔗

0
Plain text