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

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

برای نمونه، یکی از روش‌هایی که می‌توانیم به ازای $n=5, k=3$، دنباله‌‌ی اولیه را به یک عدد تبدیل کنیم، در زیر آمده است.

$$1,2,4,[5] \rightarrow 5,10,[20] \rightarrow [100],200 \rightarrow 20000 \rightarrow 2$$

اگر طول دنباله‌ی اولیه $l$ باشد، با توجه به این‌که در هر مرحله‌ باید چپ‌ترین یا راست‌ترین عدد را حذف کنیم، $2^{l-1}$ روش وجود دارد تا دنباله‌ به یک عدد تبدیل شود. برای هر یک از این روش‌ها عدد نهایی را جمع زده و یاقی‌مانده‌ی این مجموع بر $10^9 + 7$ را $f(n,k)$ می‌نامیم. لازم به ذکر است که عدد $10^9+7$، اول است.

$1$- الف ($9$ نمره) : باقی‌مانده‌ی $f(10^3, 3)$ بر $\Delta$ چند است؟

$1$- ب ($14$ نمره) : باقی‌مانده‌ی $f(10^6, 17)$ بر $\Delta$ چند است؟

$1$- ج ($17$ نمره) : باقی‌مانده‌ی $f(10^9, 257)$ بر $\Delta$ چند است؟

• سوال قبل
• سوال بعد