A. Kendama Challenge
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

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 \leq i \leq 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 \leq K \leq N \leq 2 \times 10^5$$$)

In the following $$$N$$$ lines, the $$$i$$$-th line contains integers $$$A_i, B_i$$$ separated by a space. ($$$1 \leq A_i \leq B_i \leq 998244352$$$)

Output

Output the probability modulo $$$998244353$$$ in a single line.

Examples
Input
2 2
1 1
1 2
Output
499122177
Input
5 4
1 1
1 1
1 1
1 1
1 10000
Output
1
Input
5 3
3 14
1 59
2 65
3 58
9 79
Output
62790646
Note

For the first example:

Let S denote the event that player $$$i$$$ succeeds, and F denote the event that player $$$i$$$ fails.

The possible patterns and their probabilities are as follows:

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

Only 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 \leq z \leq 998244352$$$ such that $$$xz \equiv y \pmod{998244353}$$$. Output this $$$z$$$.