נאניוואזו-קון עומד להתמודד באתגר הקנדמה המסורתי בתוכנית מוזיקה של ערב השנה החדשה. אם לפחות $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$ זה.