====== بی‌حاشیه ======



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

اعداد $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$، اول است.


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


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

<پاسخ>

1999

</پاسخ>
 


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

<پاسخ>

9017

</پاسخ>


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

<پاسخ>

2810

</پاسخ>



  * [[سوال ۲|سوال قبل]]
  * [[سوال ۴|سوال بعد]]