Naniwazu-kun 將在跨年音樂節目中挑戰傳統劍玉。如果至少有 $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

輸入格式 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

說明

對於第一個範例： 令 $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$。

對於第二個範例： 即使最後一位上場的 Naniwazu-kun 技術不佳，只要前面的幫手可靠，挑戰依然可以成功。

機率對 $998244353$ 取模的定義

可以證明所需的機率總是一個有理數。在本題的限制下，當機率表示為最簡分數 $\frac{y}{x}$ 時，保證 $x$ 不能被 $998244353$ 整除。

在這種情況下，存在唯一的整數 $z$ 滿足 $0 \le z \le 998244352$，使得 $xz \equiv y \pmod{998244353}$。 請輸出此 $z$。