ارشیا با محدودیت‌های زیادی مواجه شده و تنها برخی از جایگشت‌ها می‌توانند به دادش برسند.

ارشیا در هر بخش از این سوال یک عدد $n$ دارد که طول جایگشت مدنظر را مشخص می‌کند و برای هر یک از جایگاه‌های ۱ تا $n$ از جایگشت، یک مقدار حداقل و یک مقدار حداکثر مشخص دارد.

به دنباله‌هایی دادرس می‌گوییم که علاوه بر شرط جایگشت بودن (دقیقاً یک بار حضور اعداد طبیعی ۱ تا $n$ در آن)، اعداد موجود در جایگاه‌های آن، از محدودیت گفته شده تبعیت کند. شما باید در هر بخش از سوال به ارشیا کمک کنید و تعداد دنباله‌های دادرس را پیدا کنید.

برای مثال اگر $n$ برابر ۳ باشد و هیچ محدودیت دیگری نباشد (یعنی محدودیت حداقل همه‌ی جایگاه‌ها برابر ۱ و محدودیت حداکثر همه‌ی جایگاه‌ها برابر ۳ باشد) ۶ دنباله‌ی دادرس داریم؛ اما اگر عنصر در جایگاه ۱ حداقل ۲ باشد و عنصر جایگاه ۳ حداکثر ۲ باشد، جایگشت‌های دادرس بدین شکل خواهند بود:

$$\langle2,3,1\rangle,\langle3,1,2\rangle,\langle3,2,1\rangle$$

ورودی

یک جایگشت ۱۰۰ تایی داریم که محدودیت حداقل و حداکثر مقدار جایگاه‌های آن در فایل limited.txt قرار گرفته است؛ این فایل در ۱۰۰ خط تنظیم شده‌است که هر خط آن حاوی دو تا عدد است که عدد اول آن حداقل مقدار جایگشت در جایگاه متناظر است و عدد دوم حداکثر مقدار جایگشت در جایگاه متناظر است.

توجه داشته باشید که تنها ۲۰ خانه از آرایه هستند که محدودیت حداکثر مقدار آن‌ها برابر با ۱۰۰ نیست!

تمام پاسخ‌های ارائه شده در این سوال با فرض $\Delta = 10256483$ محاسبه شده‌اند.

$2$- الف ($33$ نمره) : فرض کنید $n$ برابر ۱۱ باشد و محدودیت حداقل مقدار جایگاه‌ها به ترتیب برابر $\langle1,2,5,3,6,1,1,2,1,2,3\rangle$ و محدودیت حداکثر مقدار جایگاه‌ها به ترتیب برابر $\langle11,10,7,9,11,7,4,8,10,11,5\rangle$ باشد. اگر تعداد جایگشت‌های دادرس برابر $k$ باشد، باقی‌مانده‌ی تقسیم عدد $k^4$ بر $\Delta$ چقدر است؟

$2$- ب ($33$ نمره) : فرض کنید $n$ برابر ۱۰۰ باشد و محدودیت حداقل مقدار جایگاه‌ها برابر محدودیت‌های درون فایل limited.txt باشد و محدودیتی برای حداکثر مقدار جایگاه‌ها نداشته باشیم! در این صورت باقی‌مانده‌ی تقسیم تعداد جایگشت‌های دادرس بر $\Delta$ چقدر است؟

$2$- ج ($34$ نمره) : فرض کنید $n$ برابر ۱۰۰ باشد و تمام محدودیت‌ها برابر محدودیت‌های درون فایل limited.txt باشند. در این صورت باقی‌مانده‌ی تقسیم تعداد جایگشت‌های دادرس بر $\Delta$ چقدر است؟ توجه کنید در فایل ورودی تنها ۲۰ تا مقدار کران بالا (حداکثر) داریم که برابر با ۱۰۰ نیستند.