يقفز الجندب على أعمدة تقع على نفس الخط على مسافات متساوية من بعضها البعض. تحتوي الأعمدة على أرقام تسلسلية من
1 إلى
N . في البداية ، يجلس الجندب على منشور يحمل الرقم
1 . يمكن أن يقفز للأمام من شريط
1 إلى
K ، بدءًا من الشريط الحالي. مطلوب للعثور على عدد الطرق التي يمكن للجندب من خلالها الوصول إلى العمود الذي يحتوي على الرقم
N . ضع في اعتبارك أن الجندب لا يمكنه القفز للخلف.
& nbsp؛
نظرًا لأن عدد طرق البحث يمكن أن يكون كبيرًا جدًا ، modulo \ (10 ^ 6 + 7 \) ، أي ابحث عن باقي القسمة لهذا الرقم \ (10 ^ 6 + 7 \) .
& nbsp؛
الإدخال: تحتوي سلسلة الإدخال على أرقام طبيعية N و K مفصولة بمسافة. نضمن أن \ (1 & lt؛ = N، \ K & lt؛ = 10000 \) .
& nbsp؛
الإخراج: & nbsp؛ يجب أن يطبع البرنامج رقمًا واحدًا: عدد الطرق التي يمكن أن يصل بها الجندب إلى العمود المرقّم N المحسوب من الوحدة النمطية \ (10 ^ 6 + 7 \) .
نبسب ؛
أمثلة
| # |
إدخال |
الإخراج |
<الجسم>
| 1 |
10 5 |
236 |
| 2 |
100 50 |
934384 |