Naniwazu-kun skal bryne seg på den tradisjonelle kendama-utfordringen i et musikkprogram på nyttårsaften. Hvis minst $K$ personer lykkes på rad, blir rekorden slått. For å maksimere sannsynligheten for å lykkes så mye som mulig, bestemte han seg for å ta utfordringen med et lag på $N$ nøye utvalgte spillere.
De $N$ spillerne vil prøve seg på kendamaen i rekkefølge fra den $1$-ste til den $N$-te. Sannsynligheten for at den $i$-te spilleren ($1 \le i \le N$) lykkes er $\frac{A_i}{B_i}$, og hver spillers suksess eller fiasko er uavhengig.
Finn sannsynligheten for at det finnes minst ett segment der $K$ eller flere påfølgende spillere lykkes, modulo $998244353$.
Input
På den første linjen gis heltallene $N, K$ adskilt med et mellomrom. ($1 \le K \le N \le 2 \times 10^5$)
På de neste $N$ linjene inneholder den $i$-te linjen heltallene $A_i, B_i$ adskilt med et mellomrom. ($1 \le A_i \le B_i \le 998244352$)
Output
Skriv ut sannsynligheten modulo $998244353$ på én enkelt linje.
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
For det første eksempelet: La $\text{S}$ betegne hendelsen at spiller $i$ lykkes, og $\text{F}$ betegne hendelsen at spiller $i$ mislykkes. De mulige mønstrene og deres sannsynligheter er som følger:
- $\text{SS} : 1 \times \frac{1}{2} = \frac{1}{2}$
- $\text{SF} : 1 \times \frac{1}{2} = \frac{1}{2}$
Bare $\text{SS}$ inneholder et segment der minst $2$ spillere lykkes på rad, og sannsynligheten for dette er $\frac{1}{2}$. Siden $499122177 \times 2 \equiv 1 \pmod{998244353}$, skriver vi ut $499122177$.
For det andre eksempelet: Selv om Naniwazu-kun, som opptrer sist, ikke er særlig dyktig, går det fint så lenge hjelperne er pålitelige.
Definisjon av sannsynlighet modulo $998244353$
Det kan bevises at den etterspurte sannsynligheten alltid er et rasjonalt tall. Under begrensningene i denne oppgaven er det garantert at $x$ ikke er delelig med $998244353$ når sannsynligheten uttrykkes som en forkortet brøk $\frac{y}{x}$.
I dette tilfellet finnes det et unikt heltall $z$ med $0 \le z \le 998244352$ slik at $xz \equiv y \pmod{998244353}$. Skriv ut denne $z$.