Naniwazu-kun is going to take on the traditional kendama challenge in a New Year's Eve music program. If at least $K$ people succeed consecutively, the record will be broken. To maximize the probability of success as much as possible, he decided to challenge it with a team of $N$ carefully selected players.
The $N$ players will attempt the kendama in order from the $1$-st to the $N$-th. The probability that the $i$-th player ($1 \le i \le N$) succeeds is $\frac{A_i}{B_i}$, and each player's success or failure is independent.
Find the probability that there exists at least one segment where $K$ or more consecutive players succeed, modulo $998244353$.
Input
In the first line, integers $N, K$ are given separated by a space. ($1 \le K \le N \le 2 \times 10^5$)
In the following $N$ lines, the $i$-th line contains integers $A_i, B_i$ separated by a space. ($1 \le A_i \le B_i \le 998244352$)
Output
Output the probability modulo $998244353$ in a single line.
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
For the first example: Let $\text{S}$ denote the event that player $i$ succeeds, and $\text{F}$ denote the event that player $i$ fails. The possible patterns and their probabilities are as follows:
- $\text{SS} : 1 \times \frac{1}{2} = \frac{1}{2}$
- $\text{SF} : 1 \times \frac{1}{2} = \frac{1}{2}$
Only $\text{SS}$ contains a segment where at least $2$ players succeed consecutively, and its probability is $\frac{1}{2}$. Since $499122177 \times 2 \equiv 1 \pmod{998244353}$, output $499122177$.
For the second example: Even if Naniwazu-kun, who performs last, is not very skilled, it is fine as long as the helpers are reliable.
Definition of probability modulo $998244353$
It can be proven that the required probability is always a rational number. Under the constraints of this problem, when the probability is expressed as a reduced fraction $\frac{y}{x}$, it is guaranteed that $x$ is not divisible by $998244353$.
In this case, there exists a unique integer $z$ with $0 \le z \le 998244352$ such that $xz \equiv y \pmod{998244353}$. Output this $z$.