Naniwazu-kun aikoo osallistua perinteiseen kendama-haasteeseen uudenvuodenaaton musiikkiohjelmassa. Jos vähintään $K$ ihmistä onnistuu peräkkäin, ennätys rikkoutuu. Maksimoidakseen onnistumistodennäköisyyden mahdollisimman suureksi hän päätti ottaa haasteen vastaan $N$ huolellisesti valitun pelaajan joukkueella.
$N$ pelaajaa yrittävät kendamaa järjestyksessä $1$-sestä $N$-nteen. Todennäköisyys sille, että $i$-s pelaaja ($1 \le i \le N$) onnistuu, on $\frac{A_i}{B_i}$, ja jokaisen pelaajan onnistuminen tai epäonnistuminen on riippumaton muista.
Etsi todennäköisyys sille, että on olemassa vähintään yksi jakso, jossa $K$ tai useampi peräkkäinen pelaaja onnistuu, modulo $998244353$.
Input
Ensimmäisellä rivillä annetaan kokonaisluvut $N, K$ välilyönnillä erotettuina. ($1 \le K \le N \le 2 \times 10^5$)
Seuraavilla $N$ rivillä $i$-s rivi sisältää kokonaisluvut $A_i, B_i$ välilyönnillä erotettuina. ($1 \le A_i \le B_i \le 998244352$)
Output
Tulosta todennäköisyys modulo $998244353$ yhdellä rivillä.
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
Ensimmäisessä esimerkissä: Merkitköön $\text{S}$ tapahtumaa, jossa pelaaja $i$ onnistuu, ja $\text{F}$ tapahtumaa, jossa pelaaja $i$ epäonnistuu. Mahdolliset kuviot ja niiden todennäköisyydet ovat seuraavat:
- $\text{SS} : 1 \times \frac{1}{2} = \frac{1}{2}$
- $\text{SF} : 1 \times \frac{1}{2} = \frac{1}{2}$
Vain $\text{SS}$ sisältää jakson, jossa vähintään $2$ pelaajaa onnistuu peräkkäin, ja sen todennäköisyys on $\frac{1}{2}$. Koska $499122177 \times 2 \equiv 1 \pmod{998244353}$, tulostetaan $499122177$.
Toisessa esimerkissä: Vaikka viimeisenä esiintyvä Naniwazu-kun ei olisikaan kovin taitava, se ei haittaa, kunhan apurit ovat luotettavia.
Todennäköisyyden modulo $998244353$ määritelmä
Voidaan todistaa, että kysytty todennäköisyys on aina rationaaliluku. Tämän tehtävän rajoitusten puitteissa on taattu, että kun todennäköisyys esitetään supistettuna murtolukuna $\frac{y}{x}$, luku $x$ ei ole jaollinen luvulla $998244353$.
Tässä tapauksessa on olemassa yksikäsitteinen kokonaisluku $z$, jolle $0 \le z \le 998244352$ ja $xz \equiv y \pmod{998244353}$. Tulosta tämä $z$.