هوشنگ تالار اسرار را کشف کرده است. این تالار از بالا به صورت یک جدول $n$ متر در $n$ متر است. همانطور که در افسانه ها آمده است، باسیلیسک در این تالار زندگی می‌کند و «هر که در چشمان او بنگرد سنگ شود». هوشنگ برای مقابله با باسیلیسک می‌خواهد از تعدادی قفسه‌ی کتاب استفاده کند. هر قفسه‌ی کتاب یک جدول $1 \times k$ است که به صورت افقی (در سطرها)‌ قرار می‌گیرد و دقیقاً $k$ خانه کامل از خانه‌های یک سطر را پر می‌کند.

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

در شکل زیر، مثال‌هایی از چینش قفسه‌ها در تالار به ازای $n = 6$ و $k = 2$ آمده است.

در شکل سمت راست امکان ندارد هوشنگ چشمان باسیلیسک را ببیند، چون باسیلیسک پایین هر ستونی باشد قفسه‌ها جلوی دیده شدنش را می‌گیریند.

ولی در شکل سمت چپ اگر باسیلیسک پایین و هوشنگ بالای ستون سوم (از راست) باشد هوشنگ چشمان باسیلیسک را می‌بیند و سنگ می‌شود.

هوشنگ از شما خواسته به او کمک کنید و به سوالات زیر پاسخ دهید.

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

$6$- الف ($11$ نمره) : اگر $n = 500$ و $k = 300$ باشد، هوشنگ به چند طریق می‌تواند این قفسه ها را قرار دهد؟ باقیمانده‌ی تقسیم این عدد بر $\Delta$ را بدست آورید.

$6$- ب ($11$ نمره) : اگر $n = 100$ و $k = 23$ باشد، هوشنگ به چند طریق می‌تواند این قفسه ها را قرار دهد؟ باقیمانده‌ی تقسیم این عدد بر $\Delta$ را بدست آورید.

$6$- ج ($12$ نمره) : اگر $n = 5000$ و $k = 1234$ باشد،‌ هوشنگ به چند طریق می‌تواند این قفسه ها را قرار دهد؟ باقیمانده‌ی تقسیم این عدد بر $\Delta$ را بدست آورید.

• سوال قبل