Naniwazu-kun ska anta den traditionella kendama-utmaningen i ett musikprogram på nyårsafton. Om minst $K$ personer lyckas i följd kommer rekordet att slås. För att maximera sannolikheten att lyckas så mycket som möjligt bestämde han sig för att anta utmaningen med ett lag bestående av $N$ noggrant utvalda spelare.
De $N$ spelarna kommer att försöka sig på kendaman i ordning från den $1$:a till den $N$:te. Sannolikheten att den $i$:te spelaren ($1 \le i \le N$) lyckas är $\frac{A_i}{B_i}$, och varje spelares framgång eller misslyckande är oberoende.
Beräkna sannolikheten att det finns minst ett segment där $K$ eller fler på varandra följande spelare lyckas, modulo $998244353$.
Input
På den första raden ges heltalen $N, K$ åtskilda av ett mellanslag. ($1 \le K \le N \le 2 \times 10^5$)
På de följande $N$ raderna innehåller den $i$:te raden heltalen $A_i, B_i$ åtskilda av ett mellanslag. ($1 \le A_i \le B_i \le 998244352$)
Output
Skriv ut sannolikheten modulo $998244353$ på en enskild rad.
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
För det första exemplet: Låt $\text{S}$ beteckna händelsen att spelare $i$ lyckas, och låt $\text{F}$ beteckna händelsen att spelare $i$ misslyckas. De möjliga mönstren och deras sannolikheter är följande:
- $\text{SS} : 1 \times \frac{1}{2} = \frac{1}{2}$
- $\text{SF} : 1 \times \frac{1}{2} = \frac{1}{2}$
Endast $\text{SS}$ innehåller ett segment där minst $2$ spelare lyckas i följd, och dess sannolikhet är $\frac{1}{2}$. Eftersom $499122177 \times 2 \equiv 1 \pmod{998244353}$, skriv ut $499122177$.
För det andra exemplet: Även om Naniwazu-kun, som uppträder sist, inte är särskilt skicklig, går det bra så länge medhjälparna är pålitliga.
Definition av sannolikhet modulo $998244353$
Det kan bevisas att den efterfrågade sannolikheten alltid är ett rationellt tal. Under begränsningarna i detta problem garanteras att $x$ inte är delbart med $998244353$ när sannolikheten uttrycks som ett förkortat bråk $\frac{y}{x}$.
I detta fall finns det ett unikt heltal $z$ med $0 \le z \le 998244352$ sådant att $xz \equiv y \pmod{998244353}$. Skriv ut detta $z$.