Naniwazu-kun affronterà la tradizionale sfida di kendama durante un programma musicale di Capodanno. Se almeno $K$ persone riescono consecutivamente, il record verrà battuto. Per massimizzare il più possibile la probabilità di successo, ha deciso di affrontare la sfida con una squadra di $N$ giocatori accuratamente selezionati.
I $N$ giocatori tenteranno il kendama in ordine dal $1$-o all'$N$-esimo. La probabilità che l'$i$-esimo giocatore ($1 \le i \le N$) riesca è $\frac{A_i}{B_i}$, e il successo o il fallimento di ciascun giocatore è indipendente.
Trova la probabilità che esista almeno un segmento in cui $K$ o più giocatori consecutivi hanno successo, modulo $998244353$.
Input
Nella prima riga sono dati gli interi $N, K$ separati da uno spazio. ($1 \le K \le N \le 2 \times 10^5$)
Nelle successive $N$ righe, l'$i$-esima riga contiene gli interi $A_i, B_i$ separati da uno spazio. ($1 \le A_i \le B_i \le 998244352$)
Output
Stampa la probabilità modulo $998244353$ su una singola riga.
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
Per il primo esempio: Sia $\text{S}$ l'evento in cui il giocatore $i$ ha successo, e $\text{F}$ l'evento in cui il giocatore $i$ fallisce. Le configurazioni possibili e le rispettive probabilità sono le seguenti:
- $\text{SS} : 1 \times \frac{1}{2} = \frac{1}{2}$
- $\text{SF} : 1 \times \frac{1}{2} = \frac{1}{2}$
Solo $\text{SS}$ contiene un segmento in cui almeno $2$ giocatori hanno successo consecutivamente, e la sua probabilità è $\frac{1}{2}$. Poiché $499122177 \times 2 \equiv 1 \pmod{998244353}$, stampa $499122177$.
Per il secondo esempio: Anche se Naniwazu-kun, che si esibisce per ultimo, non è molto abile, va tutto bene finché gli aiutanti sono affidabili.
Definizione di probabilità modulo $998244353$
Si può dimostrare che la probabilità richiesta è sempre un numero razionale. Sotto i vincoli di questo problema, quando la probabilità è espressa come frazione ridotta ai minimi termini $\frac{y}{x}$, è garantito che $x$ non è divisibile per $998244353$.
In questo caso, esiste un unico intero $z$ con $0 \le z \le 998244352$ tale che $xz \equiv y \pmod{998244353}$. Stampa questo $z$.