شخص يلعب أرقى ألعاب الهواتف المحمولة يغضب بشدة يومًا ما من اللعبة التي يضطر إلى لعبها أثناء محاولته توقيع عقد. تسير اللعبة كما يلي:
- يوجد مخزون من البطاقات يحمل الأعداد من $1$ إلى $2N+K$.
- تسحب اللعبة $N$ بطاقات واحدة تلو الأخرى من هذا المخزون، دون إعادتها، أي إن عددًا واحدًا لا يمكن سحبه مرتين.
- بعد البطاقات المسحوبة، يخمّن اللاعب ما إذا كانت البطاقة التالية ستكون أكبر أم أصغر.
ما يغضب اللاعب هو أنه، بسبب سوء حظه، يأتي باستمرار عدد أصغر بعد عدد صغير، وعدد أكبر بعد عدد كبير. لذلك يهدف اللاعب إلى منع ذلك بتعديل آلية العشوائية في اللعبة. يضيف تعديله القاعدتين التاليتين إلى سحب البطاقات:
- إذا سُحبت بطاقة تحمل عددًا من $1$ إلى $N$، فيجب أن يكون العدد على البطاقة التالية المسحوبة أكبر تمامًا من $N$ ($>N$).
- إذا سُحبت بطاقة تحمل عددًا من $N+K+1$ إلى $2N+K$، فيجب أن يكون العدد على البطاقة التالية المسحوبة أصغر تمامًا من $N+K+1$ ($<N+K+1$).
يتساءل اللاعب عن مدى إفساده اللعبة بعد هذه التعديلات. مقياس هذا الإفساد هو نسبة عدد جميع تسلسلات سحب البطاقات المختلفة الممكنة في النسخة المعدلة من اللعبة إلى عدد جميع تسلسلات سحب البطاقات الممكنة في النسخة العادية. يطلب منك هذه النسبة بترديد $10^9+7$.
تفاصيل التنفيذ
يُطلب منك تنفيذ الدالة التالية:
int oyun(int N, int K)- $N$ و$K$ عددان صحيحان يحددان مخزون البطاقات وعدد البطاقات المطلوب سحبها، كما ذُكر في المسألة.
- يجب أن تعيد هذه الدالة النسبة المطلوبة.
- ستُستدعى هذه الدالة مرة واحدة بالضبط في كل اختبار.
القيود
- $1\le N\le 10^6$
- $1\le K\le 100$
المهام الفرعية
| المهمة الفرعية | النقاط | القيود الإضافية | الاعتماديات |
|---|---|---|---|
| 1 | 10 | $1\le N,K\le 6$ | — |
| 2 | 18 | $1\le N\le 100$ | 1 |
| 3 | 6 | $1\le N\le 1000$ | 1, 2 |
| 4 | 47 | $1\le N\le 10^4$ | 1, 2, 3 |
| 5 | 19 | لا توجد قيود إضافية | 1, 2, 3, 4 |
أمثلة
oyun(2, 1)
يُتوقع أن يعيد استدعاء الدالة أعلاه $600000005$.
أعدادنا هي $1,2,3,4,5$. سنسحب بطاقتين. في الحالة العادية، يمكن سحب البطاقات بـ $20$ طريقة مختلفة. في اللعبة المعدلة، إذا كانت بطاقتنا الأولى $1$ أو $2$ أو $4$ أو $5$، فهناك $3$ احتمالات مختلفة للبطاقة الثانية؛ وإذا كانت $3$، فهناك $4$ احتمالات مختلفة للبطاقة الثانية. لذلك يوجد إجمالًا $16$ احتمالًا للعبة المعدلة. ولدينا $\frac{16}{20}=\frac45$. يكافئ هذا الاحتمال $600000005$ بترديد العدد المستخدم لدينا.
برنامج التقييم النموذجي
يتوقع برنامج التقييم النموذجي كل حالة بالصيغة التالية:
$$N\ K$$
إذا أعادت الدالة المطلوبة عددًا صحيحًا بنجاح، فسيطبع هذه النتيجة $R$ بالصيغة التالية:
$$R$$