Naniwazu-kun participará en el tradicional desafío de kendama en un programa de música de Nochevieja. Si al menos $K$ personas tienen éxito de forma consecutiva, se romperá el récord. Para maximizar la probabilidad de éxito tanto como sea posible, decidió afrontar el desafío con un equipo de $N$ jugadores cuidadosamente seleccionados.

Los $N$ jugadores intentarán el kendama en orden, desde el 1-ro hasta el $N$-ésimo. La probabilidad de que el $i$-ésimo jugador ($1 \le i \le N$) tenga éxito es $\frac{A_i}{B_i}$, y el éxito o fracaso de cada jugador es independiente.

Encuentre la probabilidad de que exista al menos un segmento donde $K$ o más jugadores consecutivos tengan éxito, módulo 998244353.

Entrada

En la primera línea, se dan los enteros $N, K$ separados por un espacio. ($1 \le K \le N \le 2 \times 10^5$)

En las siguientes $N$ líneas, la $i$-ésima línea contiene los enteros $A_i, B_i$ separados por un espacio. ($1 \le A_i \le B_i \le 998244352$)

Salida

Imprima la probabilidad módulo 998244353 en una sola línea.

Ejemplos

Entrada 1

2 2
1 1
1 2

Salida 1

499122177

Entrada 2

5 4
1 1
1 1
1 1
1 1
1 10000

Salida 2

1

Entrada 3

5 3
3 14
1 59
2 65
3 58
9 79

Salida 3

62790646

Nota

Para el primer ejemplo: Sea S el evento en el que el jugador $i$ tiene éxito, y F el evento en el que el jugador $i$ falla. Los patrones posibles y sus probabilidades son los siguientes:

• SS : $1 \times \frac{1}{2} = \frac{1}{2}$
• SF : $1 \times \frac{1}{2} = \frac{1}{2}$

Solo SS contiene un segmento donde al menos 2 jugadores tienen éxito consecutivamente, y su probabilidad es $\frac{1}{2}$. Dado que $499122177 \times 2 \equiv 1 \pmod{998244353}$, la salida es 499122177.

Para el segundo ejemplo: Incluso si Naniwazu-kun, quien actúa al final, no es muy hábil, está bien siempre y cuando los ayudantes sean confiables.

Se puede demostrar que la probabilidad requerida es siempre un número racional. Bajo las restricciones de este problema, cuando la probabilidad se expresa como una fracción irreducible $\frac{y}{x}$, se garantiza que $x$ no es divisible por 998244353.

En este caso, existe un entero único $z$ con $0 \le z \le 998244352$ tal que $xz \equiv y \pmod{998244353}$. Imprima este $z$.