گردونه

شرکت شیررضا تصمیم گرفته برای تبلیغات خود با یک مشاور تبلیغاتی معروف به نام سلتی صحبت کنند تا بتوانند فروش خود را افزایش دهند. حوزه‌ی کاری این شرکت مربوط به ساخت و فروش لوازم متفرقه و غیرمرسوم است که پرفروش‌ترین کالای آن‌ها در ۳ سال اخیر گردونه‌های خوش‌ساختشان بوده است. سلتی به طراحان شیررضا پیشنهاد می‌کند که در یک خیابان پرتردد مانند سرداد جنگل، یک مسابقه با گردونه‌هایشان برگزار کنند و به مقداری که شرکت‌کننده‌ی برتر از این مسابقه امتیاز کسب می‌کند به او کره‌ی بادام‌زمینی بدهند!

بازی پیشنهادی او به این صورت است که $n$ گردونه‌ی $m$ تکه‌ای که روی هرکدام از تکه‌های آن‌ها به ترتیب اعداد $0$ تا $m-1$ نوشته شده‌اند، در یک خط پشت سر هم قرار گرفته‌اند. هرکدام از این گردونه‌ها در ابتدا با پیکان (فلش) خود به یکی از این اعداد اشاره می‌کند.

بازی به این صورت است که فرد شرکت‌کننده هربار می‌تواند $k$ گردونه‌ی متوالی را به دلخواه انتخاب کرده و هرکدام را یک واحد در جهت ساعتگرد بچرخاند (یعنی عدد انتخابی گردونه را به پیمانه‌ی $m$ یکی زیاد کند). برای مثال اگر $n=6، m=10، k=4$ و عدد انتخابی گردونه‌ها در حالت فعلی به ترتیب $\langle 1,0,4,1,9,0\rangle$ باشد، شرکت‌کننده در یک حرکت می‌تواند چهار گردونه‌ی وسط را انتخاب کرده و عدد انتخابی گردونه‌ها را تبدیل به $\langle 1,1,5,2,0,0\rangle$ کند.

فرد شرکت‌کننده می‌تواند به تعداد دفعات دلخواه این کار را انجام دهد و در نهایت امتیاز او برابر مجموع اعداد انتخابی کل گردونه‌ها در حالت نهایی می‌شود. تیم مالی شرکت شیررضا می‌ترسند که هزینه‌ی این بازی تبلیغاتی برای آن‌ها زیاد شود و از این رو قصد دارند که حداکثر امتیاز نفر اول در این مسابقه را نسبت به حالت اولیه‌ی گردونه‌ها حساب کنند تا بتوانند بودجه‌ی مربوط به این بازی را تامین کنند.

ورودی

در خط اول ورودی سه عدد $n$ و $m$ و $k$ به ترتیب آمده‌اند. در خط بعدی $n$ عدد آمده است که عدد $i$ام نشان‌دهنده‌ی عدد انتخابی اولیه برروی گردونه‌ی $i$ام است. چهار فایل با نام‌های wheel-1.in و wheel-2.in و wheel-3.in و wheel-4.in در اختیار شما قرار داده شده‌اند که هر یک شامل ورودی برای یک زیرمسئله از سوال است. محدودیت‌های هر فایل در بخش زیرمسئله‌ها نوشته شده و اطلاعات آن‌ها از طریق خود فایل نیز قابل مشاهده است.

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

بخش اول (۲۰ نمره) : اگر جواب برای حالت توصیف شده در فایل wheel-1.in را $x$ بنامیم، مقدار $x^{10}$ را به پیمانه‌ی $\Delta$ چاپ کنید. در این فایل $n=m=10، k=3$ است.

بخش دوم (۲۱ نمره) : اگر جواب برای حالت توصیف شده در فایل wheel-2.in را $x$ بنامیم، مقدار $x^{10}$ را به پیمانه‌ی $\Delta$ چاپ کنید. در این فایل $n=m=k=403403$ است.

بخش سوم (۲۶ نمره) : اگر جواب برای حالت توصیف شده در فایل wheel-3.in را $x$ بنامیم، مقدار $x^{10}$ را به پیمانه‌ی $\Delta$ چاپ کنید. در این فایل $n=403403، m=2، k=403$ است.

بخش چهارم (۳۳ نمره) : اگر جواب برای حالت توصیف شده در فایل wheel-4.in را $x$ بنامیم، مقدار $x^{10}$ را به پیمانه‌ی $\Delta$ چاپ کنید. در این فایل $n=1403403، m=1000000403، k=403403$ است.