大晦日の歌番組で恒例のけん玉チャレンジに挑むことになった naniwazu くん。 \(K\) 人以上が連続で成功すれば記録更新です。 少しでも達成確率を高めるべく、精鋭を集めた \(N\) 人チームで挑戦することにしました。
\(N\) 人のプレイヤーが \(1\) 番目から \(N\) 番目まで順番にけん玉に挑戦します。 \(i\) 番目のプレイヤー \((1 \leq i \leq N)\) が成功する確率は \(\frac{A_i}{B_i}\) で、各プレイヤーの成功・失敗は独立です。
\(K\) 人以上連続して成功する箇所が少なくとも \(1\) つ存在する確率を \(\bmod{998244353}\) で求めてください。
\(1\) 行目に整数 \(N,K\) が空白区切りで与えられます。(\(1 \leq K \leq N \leq 2 \times 10^5\))
続く \(N\) 行のうち \(i\) 行目に、整数 \(A_i,B_i\) がこの順に空白区切りで与えられます。 (\(1 \leq A_i \leq B_i \leq 998244352\))
確率を \(\bmod{998244353}\) で \(1\) 行に出力してください。
2 21 11 2
499122177
5 41 11 11 11 11 10000
1
5 33 141 592 653 589 79
62790646
\(1\) つ目のサンプルについて:
プレイヤー \(i\) が成功する事象を S、失敗する事象を F とします。
起こりうるパターンとその確率は以下の通りです。
\(2\) 人以上連続して成功する箇所が存在するのは SS のみで、確率は \(\frac{1}{2}\) です。
\(499122177 \times 2 \equiv 1 \pmod{998244353}\) であるため、\(499122177\) を出力します。
\(2\) つ目のサンプルについて:
大トリを務めるnaniwazuくんが下手でも、助っ人が心強ければ問題ありません。
求める確率は必ず有理数になることが証明できます。また、この問題の制約下では、求める確率を既約分数 \(\frac{y}{x}\) で表したとき、\(x\) が \(998244353\) で割り切れないことが保証されます。
このとき、\(xz \equiv y \pmod{998244353}\) を満たす \(0\) 以上 \(998244352\) 以下の整数 \(z\) が一意に定まります。この \(z\) を答えてください。