Grasshopper-KMax
Problem
ملخ بر روی ستون هایی که در یک خط در فواصل مساوی از یکدیگر قرار دارند می پرد. ستون ها دارای شماره سریال از 1 تا N هستند. در ابتدا، ملخ روی یک پست با شماره 1 می نشیند. می تواند از نوارهای 1 به K به جلو بپرد و از نوار فعلی شمارش شود. باید تعداد راه‌هایی را که Grasshopper می‌تواند به ستون با عدد N برسد، پیدا کنید. به خاطر داشته باشید که Grasshopper نمی تواند به عقب بپرد.
از آنجایی که تعداد راه‌های یافتن می‌تواند بسیار زیاد باشد، ماژول \(10^6 + 7\)، یعنی باقیمانده تقسیم این عدد را پیدا کنید \(10^6 + 7\) .
ورودی: رشته ورودی حاوی اعداد طبیعی N و K است که با یک فاصله از هم جدا شده‌اند. تضمین شده است که \(1 <= N ,\ K <= 10000\).
خروجی: برنامه باید یک عدد را چاپ کند: تعداد راه هایی که Grasshopper می تواند به ستون شماره N برسد محاسبه شده است. از ماژول \(10^6+7\).
نمونه‌ها
<سر>
| # |
ورودی |
خروجی |
<بدن>
| 1 |
10 5 |
236 |
| 2 |
100 50 |
934384 |