پادشاه

سروش به تازگی به دنباله‌های «پادشاه» علاقه‌مند شده است. دنباله‌ی پادشاه، دنباله‌ای از اعداد طبیعی است که در آن هر عدد، مقسوم علیه عدد بعدی خود در دنباله است. برای مثال دنباله‌ی ٨, ۴, ٢, ٢ یک دنباله‌ی پادشاه به طول ۴ است اما دنباله‌ی ۶, ٢, ۴, ٢ دنباله‌ی پادشاه نیست.

تعداد دنباله‌های پادشاه به طول $k$ که تمام عناصر آن کمتر یا مساوی $n$ هستند را با $f(n, k)$ نشان می‌دهیم. سروش می‌خواهد روشی برای محاسبه‌ی این تابع ارائه دهد تا علاقه‌اش به این دنباله‌ها را اثبات کند. اما برای اطمینان از درستی روش خود، به دانستن مقادیر تابع برای برخی از ورودی‌ها نیاز دارد و بنابراین از شما کمک خواسته است تا این مقادیر را محاسبه کنید.

با توجه به بزرگی این مقادیر، او تابع کمکی $g(n, k)$ را برابر باقی‌مانده‌ی $f(n, k)$ بر $10^9+7$ تعریف کرده است و از شما می‌خواهد تا صرفا مقادیر تابع $g$ را محاسبه کنید. برای کمک به او، به سوالات زیر پاسخ دهید.

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

$1$- الف ($11$ نمره) : باقی‌مانده‌ی $g(50, 3)^3$ (به توان سه توجه کنید) بر $\Delta$ چند است؟

$1$- ب ($11$ نمره) : باقی‌مانده‌ی $g(10^5, 100)^3$ (به توان سه توجه کنید) بر $\Delta$ چند است؟

$1$- ج ($11$ نمره) : باقی‌مانده‌ی $g(10^5, 10^6)^3$ (به توان سه توجه کنید) بر $\Delta$ چند است؟

• سوال بعد