久莲 فتاة تحب اللعب.
حانت العطلة الصيفية أخيرًا، فقررت 久莲 دعوة أصدقائها للسباحة. وتخطط أولًا لتسييج منطقة مستطيلة من البحر أمام الشاطئ الخاص بعائلتها لتكون مكانًا للسباحة. لكن البحر يحوي أخطارًا شتى؛ فالمياه عميقة جدًا في بعض الأماكن، وتوجد قناديل بحر سامة في أماكن أخرى. وتريد أن تكون المنطقة البحرية المسيّجة آمنة بالكامل.
بعد تحليل أولي، مثّلت هذه المنطقة بشبكة مستطيلة طول قاعدتها $N$ مترًا وارتفاعها $1001$ متر. تقابل القاعدة الشاطئ الخاص بعائلتها، ويمثل كل مربع صغير أبعاده $1\times1$ متر منطقة بحرية واحدة. وطلبت من أبيها أن يفحص غدًا ما إذا كان كل مربع آمنًا. وبعد معرفة هذه المعلومات، لن يتبقى لها إلا تسييج مكان السباحة الذي تريده.
يجب أن يحقق مكان السباحة المثالي لديها الشروط الثلاثة التالية:
- يجب ضمان سلامته؛ أي يجب أن تكون كل منطقة بحرية واحدة داخله آمنة.
- يجب أن يكون مستطيلًا؛ أي يجب أن يكون شبكة جزئية أبعادها $a\times b$ من الشبكة الكاملة.
- يجب أن يكون مجاورًا للشاطئ؛ أي يجب أن تنطبق حدوده السفلية على الحدود السفلية للشبكة.
على سبيل المثال، عندما يكون $N=5$، افترض أن نتائج الفحص كما في الشكل التالي (لأن $1001$ عدد كبير جدًا، لا يظهر هنا إلا الصفوف الثلاثة السفلية، أما بقية الشبكة فخطرة).
يمكنها عندئذ اختيار المنطقة الجزئية ذات الأبعاد $1\times4$ في الصف السفلي، أو المنطقة ذات الأبعاد $3\times1$ في العمود الثالث. لاحظ أنها لا تستطيع اختيار المنطقة ذات الأبعاد $1\times5$ في الصف العلوي، لأنها غير مجاورة للشاطئ.
ولكي يستمتع أصدقاؤها، تريد أن تكون مساحة مكان السباحة أكبر ما يمكن. لذلك ستختار المنطقة ذات الأبعاد $1\times4$ في الصف السفلي لتكون خطتها النهائية.
على الرغم من أنها لن تعرف حتى الغد ما إذا كانت كل منطقة بحرية واحدة آمنة، فإنها تريد البدء الآن بتقدير مساحة مكان السباحة. وبعد تقدير بسيط، تفترض أن كل منطقة بحرية واحدة آمنة باحتمال $q$ وغير آمنة باحتمال $1-q$، بصورة مستقلة عن المناطق الأخرى. وتريد معرفة احتمال أن تكون أكبر مساحة يمكنها اختيارها لمكان السباحة مساوية بالضبط لـ $K$.
لكن 久莲 غير مهتمة بالرياضيات، ولذلك تريد منك مساعدتها في حساب هذه القيمة.
الإدخال
اقرأ البيانات من الملف pool.in.
يحتوي الإدخال على سطر واحد فيه أربعة أعداد صحيحة موجبة $N,K,x,y$، حيث $1\le x<y<998244353$. وقيمة $q$ هي $\frac{x}{y}$.
الإخراج
اكتب الناتج في الملف pool.out.
أخرج في سطر واحد عددًا صحيحًا يمثل قيمة الإجابة بترديد $998244353$.
أي إذا كانت الإجابة في أبسط صورة كسرية هي $\frac{a}{b}$، حيث $a$ و$b$ أوليان فيما بينهما، فأخرج العدد الصحيح $x$ الذي يحقق $bx\equiv a\pmod{998244353}$ و$0\le x<998244353$. يمكن إثبات أن هذا العدد الصحيح $x$ وحيد.
أمثلة
الإدخال 1
10 5 1 2
الإخراج 1
342025319
المثال 2
انظر الملفين pool/pool2.in وpool/pool2.ans في مجلد المتسابق.
المثال 3
انظر الملفين pool/pool3.in وpool/pool3.ans في مجلد المتسابق.
ملاحظة
$x^{p-1}\equiv1\pmod p$، حيث $p$ عدد أولي و$x\in[1,p)$.
المهام الفرعية
| أرقام حالات الاختبار | $N$ | $K$ |
|---|---|---|
| $1,2$ | $=1$ | $\le1000$ |
| $3$ | $\le10$ | $\le8$ |
| $4$ | $\le10$ | $\le9$ |
| $5$ | $\le10$ | $\le10$ |
| $6$ | $\le1000$ | $\le7$ |
| $7$ | $\le1000$ | $\le8$ |
| $8$ | $\le1000$ | $\le9$ |
| $9,10,11$ | $\le1000$ | $\le100$ |
| $12,13,14$ | $\le1000$ | $\le1000$ |
| $15,16$ | $\le10^9$ | $\le10$ |
| $17,18$ | $\le10^9$ | $\le100$ |
| $19,20$ | $\le10^9$ | $\le1000$ |