Нанивазу-кун собирается принять участие в традиционном соревновании по кэндаме в новогодней музыкальной программе. Если хотя бы $K$ человек подряд справятся с заданием, рекорд будет побит. Чтобы максимально увеличить вероятность успеха, он решил собрать команду из $N$ тщательно отобранных игроков.

$N$ игроков будут выполнять упражнение с кэндамой по очереди, с 1-го по $N$-й. Вероятность того, что $i$-й игрок ($1 \le i \le N$) справится с заданием, равна $\frac{A_i}{B_i}$, при этом успех или неудача каждого игрока независимы.

Найдите вероятность того, что существует хотя бы один отрезок, на котором $K$ или более игроков подряд справились с заданием, по модулю $998244353$.

Входные данные

В первой строке заданы целые числа $N, K$, разделенные пробелом ($1 \le K \le N \le 2 \times 10^5$).

В следующих $N$ строках $i$-я строка содержит целые числа $A_i, B_i$, разделенные пробелом ($1 \le A_i \le B_i \le 998244352$).

Выходные данные

Выведите вероятность по модулю $998244353$ в одной строке.

Примеры

Входные данные 1

2 2
1 1
1 2

Выходные данные 1

499122177

Примечание

Для первого примера: Пусть $S$ обозначает событие, при котором игрок $i$ справляется с заданием, а $F$ — событие, при котором игрок $i$ не справляется. Возможные исходы и их вероятности:

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

Только $SS$ содержит отрезок, где как минимум 2 игрока справились подряд, и его вероятность равна $\frac{1}{2}$. Так как $499122177 \times 2 \equiv 1 \pmod{998244353}$, выводим $499122177$.

Входные данные 2

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

Выходные данные 2

1

Примечание

Для второго примера: Даже если Нанивазу-кун, выступающий последним, не очень опытен, это не имеет значения, пока помощники надежны.

Входные данные 3

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

Выходные данные 3

62790646

Определение вероятности по модулю 998244353

Можно доказать, что искомая вероятность всегда является рациональным числом. При ограничениях данной задачи, если вероятность представлена в виде несократимой дроби $\frac{y}{x}$, гарантируется, что $x$ не делится на $998244353$.

В этом случае существует единственное целое число $z$, такое что $0 \le z \le 998244352$ и $xz \equiv y \pmod{998244353}$. Выведите это число $z$.