پس از برگزاری کلاسهای دورهی تابستانهی المپیاد کامپیوتر، زمان برگزاری امتحانات نهایی عملی رسیده است.
در این دورهی تابستانه $n$ دانشپژوه در حال دانش پژوهیدن بودند و بنابراین در امتحانات نهایی نیز $n$ دانشپژوه دانش خواهند پژوهید. در سالن برگزاری امتحانات نیز $n$ کامپیوتر برای آنها آماده شدهاست که دور یک میز دایرهای قرار گرفتهاند و به ترتیب ساعتگرد با اعداد $1$ تا $n$ شمارهگذاری شدهاند.
امیرمحمّد که خیلی دوست داشت اثری از او در امتحانات نهایی هم موجود باشد، وظیفهی خطیر مشخّص کردن جای نشستن دانشپژوهان در آزمون اوّل را برعهده گرفت. بنابراین به هر دانشپژوه یک عدد از $1$ تا $n$ نسبت داد که شمارهی کامپیوتر او را مشخّص میکرد. به عبارت دیگر یک آرایهی $a$ به طول $n$ مشخّص کرد که $a_i$ شمارهی کامپیوتر دانشپژوه $i$ام در حین آزمون را مشخّص میکرد.
امّا قضیه به همین سادگیها نبود… به دلیل پارهای از مشکلات فنّی، آرایهی $a$ شامل تعدادی عضو تکراری بود! یعنی به برخی از دانشپژوهان کامپیوتر یکسانی نسبت داده شده بود. امیرمحمّد که پیش از شروع امتحان متوجّه این ماجرا شده بود، مشکل را با مجید در میان گذاشت.
مجید تصمیم گرفت روند نشستن دانش پژوهان در سالن به این شکل باشد که ابتدا آنها پشت در سالن امتحان در یک صف بایستند؛ سپس به ترتیب از ابتدای صف وارد سالن امتحان شوند. هر گاه دانشپژوهی وارد سالن امتحان شد و دید که دانشپژوهی پشت کامپیوتر مورد نظرش نشسته است، سراغ کامپیوتر بعدی (در جهت ساعتگرد) برود. دانشپژوه باید این کار را تا زمانی ادامه دهد که به یک کامپیوتر خالی برسد و پای آن کامپیوتر بنشیند. به عبارت دیگر دانشپژوه $i$ام پشت اوّلین کامپیوتر بعد از $a_i$ (با احتساب خود $a_i$) مینشیند که در زمان وارد شدن او به سالن دانشپژوه دیگری پشتش ننشسته باشد. پس از آن که هر دانشپژوه پشت کامپیوتری نشست، نفر بعدی صف وارد سالن میشود.
به این ترتیب دانشپژوهان بدون مشکل خاصی توانستند پای کامپیوترهایشان بنشینند و آزمون با خوبی و خوشی برگزار شود. در حین برگزاری آزمون مجید ماجرای پیش آمده را برای شایان تعریف کرد. شایان که به شدّت از کمبود سوال برای امتحانات عملی رنج میبرد، تصمیم گرفت از این ماجرا هم سوالی طرح کند! شایان آرایهی $b$ به طول $n$ را تعریف کرد: $b_i$ شماره کامپیوتری است که دانشآموز $i$ام پشت آن نشسته است. سوال شایان این بود که اگر ما آرایهی $a$ و $b$ را داشته باشیم، دانشپژوهان به چند طریق میتوانند پشت در سالن امتحان صفی تشکیل دهند که پس از آن که وارد سالن شدند، دانشآموز $i$ام پشت کامپیوتر $b_i$ نشسته باشد.
شایان که باید به آمادهسازی سوالات دیگری بپردازد، از شما میخواهد این سوال را برای او حل کنید!
در سطر اول ورودی عدد $n$ آمدهاست.
در $i$امین سطر بعد، به ترتیب دو عدد $a_i$ و $b_i$ آمدهاست.
تضمین میشود که آرایهی $b$ یک جایگشت است.
در تنها خط خروجی، باقیماندهی تعداد ترتیبهای معتبر را به پیمانهی $10^9 + 7$ خروجی دهید.
| ورودی نمونه | خروجی نمونه |
|---|---|
3 2 2 3 3 2 1 | 2 |
13 1 1 2 2 3 3 4 4 6 6 5 5 7 7 8 8 9 9 10 10 11 11 12 12 13 13 | 227020758 |
4 4 4 3 1 1 2 2 3 | 0 |
نمونهی اول: تنها پس از قرار گرفتن دانشپژوهان ۱ و ۲ پشت کامپیوترشان، دانشپژوه ۳ باید وارد شود زیرا در غیر اینصورت در یکی از جایگاههای ۲ یا ۳ قرار خواهد گرفت. بنابراین تنها ترتیب وارد شدن دانشپژوهان اول و دوم حائز اهمیت است.
نمونهی دوم: هر دانشپژوه مستقل از دانشپژوهان دیگر در هر زمانی میتواند وارد سایت بشود و در همان مکان مشخص شده قرار خواهد گرفت. بنابراین تمامی $13!$ حالت ممکن مطلوب است.
نمونهی سوم: چنین حالتی امکانپذیر نیست!