Нанівадзу-кун збирається взяти участь у традиційному випробуванні з кендамою в новорічній музичній програмі. Якщо принаймні $K$ людей досягнуть успіху поспіль, рекорд буде побито. Щоб якомога більше максимізувати ймовірність успіху, він вирішив кинути виклик разом із командою з $N$ ретельно відібраних гравців.
Ці $N$ гравців пробуватимуть виконати трюк із кендамою по черзі від $1$-го до $N$-го. Ймовірність того, що $i$-й гравець ($1 \le i \le N$) досягне успіху, дорівнює $\frac{A_i}{B_i}$, а успіх чи невдача кожного гравця є незалежними.
Знайдіть ймовірність того, що існує принаймні один відрізок, де $K$ або більше послідовних гравців досягнуть успіху, за модулем $998244353$.
Input
У першому рядку через пробіл задано цілі числа $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$)
Output
Виведіть ймовірність за модулем $998244353$ в одному рядку.
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
Для першого прикладу: Нехай $\text{S}$ позначає подію, що гравець $i$ досяг успіху, а $\text{F}$ позначає подію, що гравець $i$ зазнав невдачі. Можливі варіанти та їхні ймовірності такі:
- $\text{SS} : 1 \times \frac{1}{2} = \frac{1}{2}$
- $\text{SF} : 1 \times \frac{1}{2} = \frac{1}{2}$
Лише $\text{SS}$ містить відрізок, де принаймні $2$ гравці досягли успіху поспіль, і його ймовірність становить $\frac{1}{2}$. Оскільки $499122177 \times 2 \equiv 1 \pmod{998244353}$, виведіть $499122177$.
Для другого прикладу: Навіть якщо Нанівадзу-кун, який виступає останнім, не дуже вправний, усе гаразд, доки помічники надійні.
Визначення ймовірності за модулем $998244353$
Можна довести, що шукана ймовірність завжди є раціональним числом. За обмежень цієї задачі, коли ймовірність подано у вигляді нескоротного дробу $\frac{y}{x}$, гарантується, що $x$ не ділиться на $998244353$.
У цьому випадку існує єдине ціле число $z$ з умовою $0 \le z \le 998244352$, таке що $xz \equiv y \pmod{998244353}$. Виведіть це $z$.