Universal Cup Judging System

Universal Cup

시간 제한: 2.0 s 메모리 제한: 1024 MB 총점: 100 해킹 가능 ✓
통계

Naniwazu-kun skal bryne seg på den tradisjonelle kendama-utfordringen i et musikkprogram på nyttårsaften. Hvis minst $K$ personer lykkes på rad, blir rekorden slått. For å maksimere sannsynligheten for å lykkes så mye som mulig, bestemte han seg for å ta utfordringen med et lag på $N$ nøye utvalgte spillere.

De $N$ spillerne vil prøve seg på kendamaen i rekkefølge fra den $1$-ste til den $N$-te. Sannsynligheten for at den $i$-te spilleren ($1 \le i \le N$) lykkes er $\frac{A_i}{B_i}$, og hver spillers suksess eller fiasko er uavhengig.

Finn sannsynligheten for at det finnes minst ett segment der $K$ eller flere påfølgende spillere lykkes, modulo $998244353$.

Input

På den første linjen gis heltallene $N, K$ adskilt med et mellomrom. ($1 \le K \le N \le 2 \times 10^5$)

På de neste $N$ linjene inneholder den $i$-te linjen heltallene $A_i, B_i$ adskilt med et mellomrom. ($1 \le A_i \le B_i \le 998244352$)

Output

Skriv ut sannsynligheten modulo $998244353$ på én enkelt linje.

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

For det første eksempelet: La $\text{S}$ betegne hendelsen at spiller $i$ lykkes, og $\text{F}$ betegne hendelsen at spiller $i$ mislykkes. De mulige mønstrene og deres sannsynligheter er som følger:

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

Bare $\text{SS}$ inneholder et segment der minst $2$ spillere lykkes på rad, og sannsynligheten for dette er $\frac{1}{2}$. Siden $499122177 \times 2 \equiv 1 \pmod{998244353}$, skriver vi ut $499122177$.

For det andre eksempelet: Selv om Naniwazu-kun, som opptrer sist, ikke er særlig dyktig, går det fint så lenge hjelperne er pålitelige.

Definisjon av sannsynlighet modulo $998244353$

Det kan bevises at den etterspurte sannsynligheten alltid er et rasjonalt tall. Under begrensningene i denne oppgaven er det garantert at $x$ ikke er delelig med $998244353$ når sannsynligheten uttrykkes som en forkortet brøk $\frac{y}{x}$.

I dette tilfellet finnes det et unikt heltall $z$ med $0 \le z \le 998244352$ slik at $xz \equiv y \pmod{998244353}$. Skriv ut denne $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.