Нанивадзу-кун Жаңа жыл қарсаңындағы музыкалық бағдарламада дәстүрлі кендама сынағына қатыспақшы. Егер кемінде $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$ шығарыңыз.
Екінші мысал үшін: Соңғы болып өнер көрсететін Нанивадзу-кун аса шебер болмаса да, көмекшілер сенімді болса болғаны.
$998244353$ модулі бойынша ықтималдықтың анықтамасы
Ізделінді ықтималдық әрқашан рационал сан болатынын дәлелдеуге болады. Осы есептің шектеулерінде ықтималдық қысқартылмайтын $\frac{y}{x}$ бөлшегі түрінде өрнектелгенде, $x$ саны $998244353$-ке бөлінбейтініне кепілдік беріледі.
Бұл жағдайда $xz \equiv y \pmod{998244353}$ болатындай $0 \le z \le 998244352$ шартын қанағаттандыратын жалғыз бүтін $z$ саны табылады. Осы $z$ санын шығарыңыз.