Naniwazu-kun akan mengikuti tantangan kendama tradisional dalam acara musik Malam Tahun Baru. Jika setidaknya $K$ orang berhasil secara berturut-turut, rekor akan terpecahkan. Untuk memaksimalkan peluang keberhasilan sebanyak mungkin, ia memutuskan untuk menantangnya bersama tim yang terdiri dari $N$ pemain pilihan.
Ke-$N$ pemain tersebut akan mencoba kendama secara berurutan mulai dari pemain ke-$1$ hingga ke-$N$. Peluang pemain ke-$i$ ($1 \le i \le N$) berhasil adalah $\frac{A_i}{B_i}$, dan keberhasilan atau kegagalan setiap pemain bersifat saling bebas.
Carilah peluang bahwa terdapat setidaknya satu segmen di mana $K$ atau lebih pemain berturut-turut berhasil, modulo $998244353$.
Input
Pada baris pertama, diberikan bilangan bulat $N, K$ yang dipisahkan oleh spasi. ($1 \le K \le N \le 2 \times 10^5$)
Pada $N$ baris berikutnya, baris ke-$i$ berisi bilangan bulat $A_i, B_i$ yang dipisahkan oleh spasi. ($1 \le A_i \le B_i \le 998244352$)
Output
Keluarkan peluang modulo $998244353$ dalam satu baris.
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
Untuk contoh pertama: Misalkan $\text{S}$ menyatakan kejadian bahwa pemain $i$ berhasil, dan $\text{F}$ menyatakan kejadian bahwa pemain $i$ gagal. Pola-pola yang mungkin beserta peluangnya adalah sebagai berikut:
- $\text{SS} : 1 \times \frac{1}{2} = \frac{1}{2}$
- $\text{SF} : 1 \times \frac{1}{2} = \frac{1}{2}$
Hanya $\text{SS}$ yang memuat segmen di mana setidaknya $2$ pemain berhasil secara berturut-turut, dan peluangnya adalah $\frac{1}{2}$. Karena $499122177 \times 2 \equiv 1 \pmod{998244353}$, keluarkan $499122177$.
Untuk contoh kedua: Meskipun Naniwazu-kun yang tampil terakhir tidak terlalu mahir, tidak masalah selama para pembantunya dapat diandalkan.
Definisi peluang modulo $998244353$
Dapat dibuktikan bahwa peluang yang diminta selalu merupakan bilangan rasional. Di bawah batasan masalah ini, ketika peluang dinyatakan sebagai pecahan paling sederhana $\frac{y}{x}$, dijamin bahwa $x$ tidak habis dibagi $998244353$.
Dalam hal ini, terdapat bilangan bulat unik $z$ dengan $0 \le z \le 998244352$ sedemikian sehingga $xz \equiv y \pmod{998244353}$. Keluarkan nilai $z$ ini.