Universal Cup Judging System

Universal Cup

Time Limit: 2.0 s Memory Limit: 1024 MB Total points: 100 Hackable ✓
Statistics

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

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
#1522EditorialOpen题解jianglyView

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.