Universal Cup Judging System

Universal Cup

Süre Sınırı: 2.0 s Bellek Sınırı: 1024 MB Toplam puan: 100 Hack'lenebilir ✓
İstatistikler

Naniwazu-kun wird in einer Silvester-Musiksendung an der traditionellen Kendama-Herausforderung teilnehmen. Wenn mindestens $K$ Personen hintereinander erfolgreich sind, wird der Rekord gebrochen. Um die Erfolgswahrscheinlichkeit so weit wie möglich zu maximieren, hat er beschlossen, die Herausforderung mit einem Team aus $N$ sorgfältig ausgewählten Spielern anzugehen.

Die $N$ Spieler versuchen sich der Reihe nach vom $1$-ten bis zum $N$-ten am Kendama. Die Wahrscheinlichkeit, dass der $i$-te Spieler ($1 \le i \le N$) Erfolg hat, beträgt $\frac{A_i}{B_i}$, und Erfolg oder Misserfolg jedes Spielers sind voneinander unabhängig.

Bestimme die Wahrscheinlichkeit, dass es mindestens einen Abschnitt gibt, in dem $K$ oder mehr aufeinanderfolgende Spieler erfolgreich sind, modulo $998244353$.

Input

In der ersten Zeile werden die ganzen Zahlen $N, K$ durch ein Leerzeichen getrennt gegeben. ($1 \le K \le N \le 2 \times 10^5$)

In den folgenden $N$ Zeilen enthält die $i$-te Zeile die ganzen Zahlen $A_i, B_i$, getrennt durch ein Leerzeichen. ($1 \le A_i \le B_i \le 998244352$)

Output

Gib die Wahrscheinlichkeit modulo $998244353$ in einer einzigen Zeile aus.

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

Zum ersten Beispiel: Sei $\text{S}$ das Ereignis, dass Spieler $i$ Erfolg hat, und $\text{F}$ das Ereignis, dass Spieler $i$ scheitert. Die möglichen Muster und ihre Wahrscheinlichkeiten lauten wie folgt:

  • $\text{SS} : 1 \times \frac{1}{2} = \frac{1}{2}$
  • $\text{SF} : 1 \times \frac{1}{2} = \frac{1}{2}$

Nur $\text{SS}$ enthält einen Abschnitt, in dem mindestens $2$ Spieler hintereinander erfolgreich sind, und seine Wahrscheinlichkeit beträgt $\frac{1}{2}$. Da $499122177 \times 2 \equiv 1 \pmod{998244353}$ gilt, ist $499122177$ auszugeben.

Zum zweiten Beispiel: Selbst wenn Naniwazu-kun, der als Letzter antritt, nicht besonders geschickt ist, macht das nichts, solange die Helfer zuverlässig sind.

Definition der Wahrscheinlichkeit modulo $998244353$

Es lässt sich beweisen, dass die gesuchte Wahrscheinlichkeit immer eine rationale Zahl ist. Unter den Bedingungen dieser Aufgabe ist garantiert, dass $x$ nicht durch $998244353$ teilbar ist, wenn die Wahrscheinlichkeit als gekürzter Bruch $\frac{y}{x}$ dargestellt wird.

In diesem Fall existiert eine eindeutige ganze Zahl $z$ mit $0 \le z \le 998244352$, sodass $xz \equiv y \pmod{998244353}$ gilt. Gib dieses $z$ aus.

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.