なにわづ君は、大晦日の音楽番組で伝統的なけん玉チャレンジに挑戦しようとしています。少なくとも $K$ 人が連続して成功すれば、記録が更新されます。成功の確率を最大限に高めるため、彼は $N$ 人の厳選されたプレイヤーでチームを組んで挑戦することにしました。

$N$ 人のプレイヤーは、1 番目から $N$ 番目まで順番にけん玉に挑戦します。$i$ 番目のプレイヤー ($1 \le i \le N$) が成功する確率は $\frac{A_i}{B_i}$ であり、各プレイヤーの成功・失敗は独立です。

$K$ 人以上が連続して成功する区間が少なくとも 1 つ存在する確率を、998244353 で割った余りを求めてください。

入力

1 行目に、整数 $N, K$ がスペース区切りで与えられます。($1 \le K \le N \le 2 \times 10^5$)

続く $N$ 行の各行には、整数 $A_i, B_i$ がスペース区切りで与えられます。($1 \le A_i \le B_i \le 998244352$)

出力

確率を 998244353 で割った余りを 1 行で出力してください。

入出力例

入力 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

注記

最初の例について： プレイヤー $i$ が成功する事象を $S$、失敗する事象を $F$ とします。 起こりうるパターンとその確率は以下の通りです。

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

少なくとも 2 人が連続して成功する区間を含むのは $SS$ のみであり、その確率は $\frac{1}{2}$ です。 $499122177 \times 2 \equiv 1 \pmod{998244353}$ なので、$499122177$ を出力します。

2 番目の例について： 最後に挑戦するなにわづ君があまり上手でなくても、助っ人が信頼できるなら問題ありません。

確率の 998244353 を法とする定義

求める確率は常に有理数になることが証明できます。この問題の制約下では、確率を既約分数 $\frac{y}{x}$ と表したとき、$x$ は 998244353 で割り切れないことが保証されています。

この場合、$xz \equiv y \pmod{998244353}$ を満たす $0 \le z \le 998244352$ を満たす整数 $z$ が一意に存在します。この $z$ を出力してください。