Background

After a month of intense practice on Codeforces, Atom has honed his skills and is finally ready for an official contest. However, fate still seems to have a challenge in store for him…

Problem Statement

Due to certain special and indescribable reasons, Atom is forced to skip exactly $k$ of Professor E’s classes. The timing of these events is random, and for Atom, each class has an equal probability of being skipped, with the total number of missed classes exactly equal to $k$.

Atom has a predictive model that estimates the probability $p_i$ of being called upon in each class by Professor E, where $p_i = \frac{a_i}{b_i}$. Atom wants to calculate the expected number of times he will be called upon when he’s absent (i.e., the expected number of missed classes where he’s called upon), with the result modulo $998244353$.

Input

The input consists of $n+1$ lines:

• The first line contains two positive integers $n$ and $k$, representing the total number of classes and the number of classes Atom will skip.
• The next $n$ lines each contain two integers $a_i$ and $b_i$, representing the probability $p_i = \frac{a_i}{b_i}$ that Atom will be called upon in the $i^{th}$ class.

Output

Output a single integer, the expected number of times Atom will be called upon while absent, modulo $998244353$.

Example

Input 1

3 1
0 1
0 1
6 6

Output 1

332748118

Example Explanation

Atom has 3 classes, and he needs to skip 1 class. Therefore, the probability of being forced to skip each class is $\frac{1}{3}$, and the probabilities of being called in each class are $0, 0,$ and $1$, respectively.

The only situation in which he will be caught is if he skips the 3rd class, with a probability of $\frac{1}{3} \times 1 = \frac{1}{3}$.

In modulo $998244353$, $\frac{1}{3}$ is represented as $332748118$.

Constraints

• $1 \leq k \leq n \leq 5 \times 10^5$
• $0 \leq a_i \leq b_i \leq 10^6$, and $b_i \neq 0$

In the modulo $998244353$ context, $\frac{a}{b}$ can be represented as $a \times b^{-1}$, where $b^{-1}$ is the modular inverse of $b$ modulo $998244353$.

Hint: Fermat's Little Theorem is a useful tool in number theory. For a prime $p$, if an integer $a$ is not divisible by $p$, then $a^{p-1} \equiv 1 \pmod{p}$, which implies that $a \times a^{p-2} \equiv 1 \pmod{p}$. Therefore, $a^{p-2}$ is the modular inverse of $a$ modulo $p$.