Naniwazu-kun ætlar að takast á við hina hefðbundnu kendama-áskorun í tónlistarþætti á gamlárskvöld. Ef að minnsta kosti $K$ manns tekst ætlunarverkið í röð verður metið slegið. Til að hámarka líkurnar á árangri eins mikið og mögulegt er ákvað hann að taka áskoruninni með liði af $N$ vandlega völdum leikmönnum.
Leikmennirnir $N$ munu reyna við kendama-leikfangið í röð frá þeim $1$-sta til þess $N$-ta. Líkurnar á að $i$-ti leikmaðurinn ($1 \le i \le N$) nái árangri eru $\frac{A_i}{B_i}$, og árangur eða mistök hvers leikmanns eru óháð öðrum.
Finndu líkurnar á að til sé að minnsta kosti eitt tímabil þar sem $K$ eða fleiri leikmenn í röð ná árangri, modulo $998244353$.
Input
Í fyrstu línunni eru gefnar heiltölurnar $N, K$ aðskildar með bili. ($1 \le K \le N \le 2 \times 10^5$)
Í næstu $N$ línum inniheldur $i$-ta línan heiltölurnar $A_i, B_i$ aðskildar með bili. ($1 \le A_i \le B_i \le 998244352$)
Output
Prentaðu líkurnar modulo $998244353$ í einni línu.
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
Fyrir fyrsta dæmið: Látum $\text{S}$ tákna þann atburð að leikmaður $i$ nái árangri, og $\text{F}$ tákna þann atburð að leikmaður $i$ mistakist. Möguleg mynstur og líkur þeirra eru sem hér segir:
- $\text{SS} : 1 \times \frac{1}{2} = \frac{1}{2}$
- $\text{SF} : 1 \times \frac{1}{2} = \frac{1}{2}$
Aðeins $\text{SS}$ inniheldur tímabil þar sem að minnsta kosti $2$ leikmenn ná árangri í röð, og líkur þess eru $\frac{1}{2}$. Þar sem $499122177 \times 2 \equiv 1 \pmod{998244353}$, skal prenta $499122177$.
Fyrir annað dæmið: Jafnvel þótt Naniwazu-kun, sem kemur síðastur fram, sé ekki mjög fær, þá er það í lagi svo lengi sem aðstoðarmennirnir eru áreiðanlegir.
Skilgreining á líkum modulo $998244353$
Hægt er að sanna að umbeðnar líkur eru alltaf ræð tala. Undir skorðum þessa verkefnis, þegar líkurnar eru settar fram sem fullstytt brot $\frac{y}{x}$, er tryggt að $x$ sé ekki deilanlegt með $998244353$.
Í þessu tilviki er til ótvírætt ákvörðuð heiltala $z$ með $0 \le z \le 998244352$ þannig að $xz \equiv y \pmod{998244353}$. Prentaðu þetta $z$.