นานิวะซึคุงกำลังจะเข้าร่วมการท้าทายเคนดามะแบบดั้งเดิมในรายการเพลงคืนวันสิ้นปี หากมีคนทำสำเร็จติดต่อกันอย่างน้อย $K$ คน สถิติจะถูกทำลาย เพื่อเพิ่มความน่าจะเป็นที่จะทำสำเร็จให้มากที่สุด เขาจึงตัดสินใจท้าทายด้วยทีมผู้เล่น $N$ คนที่คัดเลือกมาอย่างดี
ผู้เล่นทั้ง $N$ คนจะพยายามเล่นเคนดามะตามลำดับตั้งแต่คนที่ $1$ ถึงคนที่ $N$ ความน่าจะเป็นที่ผู้เล่นคนที่ $i$ ($1 \le i \le N$) จะทำสำเร็จคือ $\frac{A_i}{B_i}$ และความสำเร็จหรือความล้มเหลวของผู้เล่นแต่ละคนเป็นอิสระต่อกัน
จงหาความน่าจะเป็นที่จะมีช่วงอย่างน้อยหนึ่งช่วงที่มีผู้เล่นทำสำเร็จติดต่อกันตั้งแต่ $K$ คนขึ้นไป มอดูโล $998244353$
Input
ในบรรทัดแรก มีจำนวนเต็ม $N, K$ คั่นด้วยช่องว่าง ($1 \le K \le N \le 2 \times 10^5$)
ใน $N$ บรรทัดถัดไป บรรทัดที่ $i$ มีจำนวนเต็ม $A_i, B_i$ คั่นด้วยช่องว่าง ($1 \le A_i \le B_i \le 998244352$)
Output
แสดงผลความน่าจะเป็นมอดูโล $998244353$ ในบรรทัดเดียว
Examples
Input 1
2 2 1 1 1 2
Output 1
499122177
Input 2
5 4 1 1 1 1 1 1 1 1 1 10000
Output 2
1
Input 3
5 3 3 14 1 59 2 65 3 58 9 79
Output 3
62790646
Note
สำหรับตัวอย่างแรก: ให้ $\text{S}$ แทนเหตุการณ์ที่ผู้เล่นคนที่ $i$ ทำสำเร็จ และ $\text{F}$ แทนเหตุการณ์ที่ผู้เล่นคนที่ $i$ ทำล้มเหลว รูปแบบที่เป็นไปได้และความน่าจะเป็นของแต่ละรูปแบบมีดังนี้:
- $\text{SS} : 1 \times \frac{1}{2} = \frac{1}{2}$
- $\text{SF} : 1 \times \frac{1}{2} = \frac{1}{2}$
มีเพียง $\text{SS}$ เท่านั้นที่มีช่วงที่ผู้เล่นอย่างน้อย $2$ คนทำสำเร็จติดต่อกัน และความน่าจะเป็นของมันคือ $\frac{1}{2}$ เนื่องจาก $499122177 \times 2 \equiv 1 \pmod{998244353}$ จึงแสดงผล $499122177$
สำหรับตัวอย่างที่สอง: แม้ว่านานิวะซึคุงซึ่งแสดงเป็นคนสุดท้ายจะไม่ค่อยเก่งนัก แต่ก็ไม่เป็นไรตราบใดที่ผู้ช่วยพึ่งพาได้
นิยามของความน่าจะเป็นมอดูโล $998244353$
สามารถพิสูจน์ได้ว่าความน่าจะเป็นที่ต้องการเป็นจำนวนตรรกยะเสมอ ภายใต้ข้อจำกัดของปัญหานี้ เมื่อเขียนความน่าจะเป็นในรูปเศษส่วนอย่างต่ำ $\frac{y}{x}$ รับประกันว่า $x$ จะไม่ถูกหารด้วย $998244353$ ลงตัว
ในกรณีนี้ จะมีจำนวนเต็ม $z$ เพียงตัวเดียวที่ $0 \le z \le 998244352$ ซึ่งทำให้ $xz \equiv y \pmod{998244353}$ จงแสดงผลค่า $z$ นี้