久莲 היא ילדה שאוהבת לשחק.
חופשת הקיץ סוף־סוף הגיעה, ו־久莲 החליטה להזמין את חבריה לשחות. היא מתכננת לתחום אזור מלבני בים מול החוף הפרטי של משפחתה שישמש אזור שחייה. אולם בים יש סכנות רבות: במקומות מסוימים המים עמוקים מדי, ובאחרים יש מדוזות ארסיות. היא רוצה שכל אזור הים התחום יהיה בטוח.
לאחר ניתוח ראשוני, היא מייצגת את אזור הים כרשת מלבנית שאורך בסיסה $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.
הדפיסו שורה אחת ובה מספר שלם אחד המייצג את התשובה מודולו $998\,244\,353$.
כלומר, נניח שהתשובה כשבר מצומצם היא $\frac{a}{b}$, כאשר $a,b$ זרים. הדפיסו מספר שלם $x$ המקיים $bx\equiv a\pmod{998\,244\,353}$ וגם $0\le x<998\,244\,353$. ניתן להוכיח שמספר שלם כזה $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$ |