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.