Naniwazu-kun 準備喺除夕音樂節目入面參加傳統嘅劍玉挑戰。如果有至少 $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$。
對於第二個範例: 就算最後出場嘅 Naniwazu-kun 技術唔係幾好,只要啲幫手夠穩陣就冇問題。
概率對 $998244353$ 取模嘅定義
可以證明所求嘅概率一定係有理數。喺本題嘅限制條件下,當概率表示為最簡分數 $\frac{y}{x}$ 嗰陣,保證 $x$ 唔能夠被 $998244353$ 整除。
喺呢種情況下,存在唯一嘅整數 $z$ 滿足 $0 \le z \le 998244352$ 且 $xz \equiv y \pmod{998244353}$。請輸出呢個 $z$。