久莲 เป็นเด็กผู้หญิงที่ชอบเล่นสนุก
ในที่สุดวันหยุดฤดูร้อนก็มาถึง 久莲 ตัดสินใจชวนเพื่อน ๆ มาว่ายน้ำ เธอวางแผนจะกั้นพื้นที่ทะเลรูปสี่เหลี่ยมผืนผ้าสักแห่งนอกชายหาดส่วนตัวของครอบครัวเพื่อใช้เป็นสระว่ายน้ำ แต่ในทะเลมีอันตรายหลากหลายแบบ บางแห่งน้ำลึกเกินไป บางแห่งมีแมงกะพรุนมีพิษ เธอต้องการให้พื้นที่ทะเลที่กั้นไว้ปลอดภัยทั้งหมด
หลังจากวิเคราะห์เบื้องต้น เธอจำลองพื้นที่ทะเลนี้เป็นตารางรูปสี่เหลี่ยมผืนผ้าที่มีฐานยาว $N$ เมตร และสูง $1001$ เมตร โดยด้านล่างของตารางตรงกับชายหาดส่วนตัวของครอบครัว สี่เหลี่ยมจัตุรัสเล็กแต่ละช่องขนาด $1\times 1$ แทนพื้นที่ทะเลหนึ่งหน่วย เธอขอให้พ่อไปตรวจสอบในวันพรุ่งนี้ว่าสี่เหลี่ยมเล็กแต่ละช่องปลอดภัยหรือไม่ หลังจากทราบข้อมูลแล้ว สิ่งที่เธอต้องทำก็คือกั้นพื้นที่สระว่ายน้ำที่ต้องการ
สระว่ายน้ำในอุดมคติของเธอต้องเป็นไปตามเงื่อนไขสามข้อดังต่อไปนี้:
- ต้องรับประกันความปลอดภัย กล่าวคือ พื้นที่ทะเลทุกหน่วยในสระว่ายน้ำต้องปลอดภัย
- ต้องเป็นรูปสี่เหลี่ยมผืนผ้า กล่าวคือ สระว่ายน้ำต้องเป็นตารางย่อยขนาด $a\times b$ ของตารางทั้งหมด
- ต้องอยู่ติดกับชายหาด กล่าวคือ ขอบล่างของสระว่ายน้ำต้องแนบกับขอบล่างของตาราง
ตัวอย่างเช่น เมื่อ $N=5$ หากผลการตรวจสอบเป็นดังรูปต่อไปนี้ (เนื่องจาก $1001$ มากเกินไป จึงแสดงข้อมูลเพียงสามแถวล่างสุดของตาราง ส่วนอื่นทั้งหมดเป็นอันตราย)
เธอสามารถเลือกพื้นที่ทะเลย่อยขนาด $1\times 4$ ในแถวล่างสุด หรือพื้นที่ทะเลย่อยขนาด $3\times 1$ ในคอลัมน์ที่สามก็ได้ โปรดสังเกตว่าเธอไม่สามารถเลือกพื้นที่ทะเลย่อยขนาด $1\times 5$ ในแถวบนสุดได้ เพราะพื้นที่นั้นไม่ได้อยู่ติดกับชายหาด
เพื่อให้เพื่อน ๆ สนุกสนาน เธอต้องการให้สระว่ายน้ำมีพื้นที่มากที่สุดเท่าที่เป็นไปได้ ดังนั้นเธอจะเลือกพื้นที่ทะเลย่อยขนาด $1\times 4$ ในแถวล่างสุดเป็นคำตอบสุดท้าย
แม้ว่าเธอจะทราบในวันพรุ่งนี้เท่านั้นว่าพื้นที่ทะเลแต่ละหน่วยปลอดภัยหรือไม่ แต่เธอต้องการเริ่มประมาณขนาดพื้นที่ของสระว่ายน้ำตั้งแต่ตอนนี้ หลังจากประมาณอย่างง่าย เธอสมมติว่าพื้นที่ทะเลแต่ละหน่วยมีความน่าจะเป็นที่จะปลอดภัยเท่ากับ $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}\equiv 1\pmod p$ โดย $p$ เป็นจำนวนเฉพาะ และ $x\in[1,p)$
งานย่อย
| หมายเลขกรณีทดสอบ | $N$ | $K$ |
|---|---|---|
| $1,2$ | $=1$ | $\le 1000$ |
| $3$ | $\le 10$ | $\le 8$ |
| $4$ | $\le 10$ | $\le 9$ |
| $5$ | $\le 10$ | $\le 10$ |
| $6$ | $\le 1000$ | $\le 7$ |
| $7$ | $\le 1000$ | $\le 8$ |
| $8$ | $\le 1000$ | $\le 9$ |
| $9,10,11$ | $\le 1000$ | $\le 100$ |
| $12,13,14$ | $\le 1000$ | $\le 1000$ |
| $15,16$ | $\le 10^9$ | $\le 10$ |
| $17,18$ | $\le 10^9$ | $\le 100$ |
| $19,20$ | $\le 10^9$ | $\le 1000$ |