Universal Cup Judging System

Universal Cup

时间限制: 2.0 s 内存限制: 1024 MB 总分: 100 可 Hack ✓
统计

Нанивадзу-кун Жаңа жыл қарсаңындағы музыкалық бағдарламада дәстүрлі кендама сынағына қатыспақшы. Егер кемінде $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$ санын шығарыңыз.

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
#1522EditorialOpen题解jianglyView

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.