Naniwazu-kun bierze udział w tradycyjnym wyzwaniu kendama w sylwestrowym programie muzycznym. Jeśli co najmniej $K$ osób odniesie sukces z rzędu, rekord zostanie pobity. Aby zmaksymalizować prawdopodobieństwo sukcesu, zdecydował się podjąć wyzwanie z zespołem $N$ starannie dobranych graczy.

$N$ graczy będzie próbować wykonać kendamę w kolejności od 1. do $N$-tego. Prawdopodobieństwo, że $i$-ty gracz ($1 \le i \le N$) odniesie sukces, wynosi $\frac{A_i}{B_i}$, a sukces lub porażka każdego gracza są niezależne.

Oblicz prawdopodobieństwo, że istnieje co najmniej jeden segment, w którym $K$ lub więcej graczy z rzędu odniesie sukces, modulo 998244353.

Wejście

W pierwszej linii podano liczby całkowite $N, K$ oddzielone spacją ($1 \le K \le N \le 2 \times 10^5$).

W kolejnych $N$ liniach, $i$-ta linia zawiera liczby całkowite $A_i, B_i$ oddzielone spacją ($1 \le A_i \le B_i \le 998244352$).

Wyjście

Wypisz prawdopodobieństwo modulo 998244353 w pojedynczej linii.

Przykład

Wejście 1

2 2
1 1
1 2

Wyjście 1

499122177

Wejście 2

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

Wyjście 2

1

Wejście 3

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

Wyjście 3

62790646

Uwagi

Dla pierwszego przykładu:

Niech $S$ oznacza zdarzenie, w którym gracz $i$ odnosi sukces, a $F$ oznacza zdarzenie, w którym gracz $i$ ponosi porażkę.

Możliwe wzorce i ich prawdopodobieństwa są następujące:

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

Tylko $SS$ zawiera segment, w którym co najmniej 2 graczy odnosi sukces z rzędu, a jego prawdopodobieństwo wynosi $\frac{1}{2}$.

Ponieważ $499122177 \times 2 \equiv 1 \pmod{998244353}$, wypisujemy 499122177.

Dla drugiego przykładu:

Nawet jeśli Naniwazu-kun, który występuje ostatni, nie jest zbyt wykwalifikowany, jest w porządku, o ile pomocnicy są niezawodni.

Definicja prawdopodobieństwa modulo 998244353

Można udowodnić, że wymagane prawdopodobieństwo jest zawsze liczbą wymierną. Przy ograniczeniach tego zadania, gdy prawdopodobieństwo jest wyrażone jako nieskracalny ułamek $\frac{y}{x}$, gwarantuje się, że $x$ nie jest podzielne przez 998244353.

W takim przypadku istnieje unikalna liczba całkowita $z$ taka, że $0 \le z \le 998244352$ oraz $xz \equiv y \pmod{998244353}$. Wypisz to $z$.