یک جدول $n \times n$ داریم. می‌خواهیم در تعدادی از خانه‌های جدول رخ قرار دهیم به طوری که در هر خانه حداکثر یک رخ قرار گیرد. یک چیدمان را \textbf{مطلوب} می‌نامیم اگر در هر سطر و در هر ستون جدول دقیقاً دو رخ وجود داشته باشد. دو چیدمان زمانی متفاوت‌اند که دست‌کم یک خانه در یکی از آن‌ها دارای رخ و در دیگری خالی باشد.

تعداد چیدمان‌های مطلوب جدول $n\times n$ را با $A_n$ نشان می‌دهیم. در سه بخش اول، باقی‌مانده‌ی $A_n$ بر $\Delta$ را چاپ کنید.

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

بخش اول (۹ نمره): $n=4$ است.

بخش دوم (۳۴ نمره): $n=1000$ است.

بخش سوم (۴۱ نمره): $n=10^6$ است.

بخش چهارم (۱۶ نمره): باقی‌مانده‌ی $\displaystyle\sum_{n=1}^{10^6} A_n$ بر $\Delta$ را چاپ کنید.