خیر الامور

پرشا علاقه‌ی شدیدی به جایگشت‌ها¹⁾ دارد. پرشا به تازگی با مفهومی به نام «میانه» بر روی یک آرایه آشنا شده که تعریف آن بدین صورت است: «به عضوی در یک آرایه‌ی $n$ عضوی که مقدار آن در آرایه‌ی مرتب‌شده در خانه‌ی $\left\lceil\frac{n+1}{2}\right\rceil$ قرار می‌گیرد، عضو میانه می‌گوییم».

به عنوان مثال میانه‌ی آرایه‌ی $\langle3,2,4\rangle$ برابر با $3$ و میانه‌ی آرایه‌ی $\langle10,20,30,40\rangle$ برابر با $30$ است. او به دنبال پیدا کردن جایگشت موردعلاقه‌ی خود مفهومی دیگر به نام «معنویت» بر روی یک آرایه را بدین گونه تعریف کرد: «معنویتِ یک جایگشت برابر با کمترین مقدار میانه به ازای تمام پیشوندهای²⁾ جایگشت اولیه است».

یک روز پرشا از سر بیکاری شروع به نوشتن تمام جایگشت‌های اعداد $1$ تا $n$ می‌کند و معنویت تمام آن‌ها را حساب کرده و جمع آن‌ها را روی یک ورق یادداشت می‌کند. او بسیار نگران این شده که اشتباهی در محاسبات معنویت تعدادی از جایگشت‌ها داشته باشد که باعث اشتباه در انتخاب جایگشت مورد علاقه‌اش شود. از این رو، از شما درخواست کرده است که این مقدار را حساب کنید تا اگر اشتباهی کرده باشد محاسبات خود را دوباره انجام دهد تا به عدد نهایی شما برسد.

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

بخش اول (۱۱ نمره) : اگر پاسخ مسئله به ازای $n=5$ برابر با $x$ باشد، حاصل $x^8$ را به پیمانه‌ی $\Delta$ خروجی دهید.

بخش دوم (۲۲ نمره) : اگر پاسخ مسئله به ازای $n=500$ برابر با $x$ باشد، حاصل $x^8$ را به پیمانه‌ی $\Delta$ خروجی دهید.

بخش سوم (۲۴ نمره) : اگر پاسخ مسئله به ازای $n=10^4$ برابر با $x$ باشد، حاصل $x^8$ را به پیمانه‌ی $\Delta$ خروجی دهید.

بخش چهارم (۴۳ نمره) : اگر پاسخ مسئله به ازای $n=10^6$ برابر با $x$ باشد، حاصل $x^8$ را به پیمانه‌ی $\Delta$ خروجی دهید.