Universal Cup Judging System

Universal Cup

Límite de tiempo: 2.0 s Límite de memoria: 1024 MB Puntuación total: 100 Hackeable ✓
Estadísticas

Naniwazu-kun ska anta den traditionella kendama-utmaningen i ett musikprogram på nyårsafton. Om minst $K$ personer lyckas i följd kommer rekordet att slås. För att maximera sannolikheten att lyckas så mycket som möjligt bestämde han sig för att anta utmaningen med ett lag bestående av $N$ noggrant utvalda spelare.

De $N$ spelarna kommer att försöka sig på kendaman i ordning från den $1$:a till den $N$:te. Sannolikheten att den $i$:te spelaren ($1 \le i \le N$) lyckas är $\frac{A_i}{B_i}$, och varje spelares framgång eller misslyckande är oberoende.

Beräkna sannolikheten att det finns minst ett segment där $K$ eller fler på varandra följande spelare lyckas, modulo $998244353$.

Input

På den första raden ges heltalen $N, K$ åtskilda av ett mellanslag. ($1 \le K \le N \le 2 \times 10^5$)

På de följande $N$ raderna innehåller den $i$:te raden heltalen $A_i, B_i$ åtskilda av ett mellanslag. ($1 \le A_i \le B_i \le 998244352$)

Output

Skriv ut sannolikheten modulo $998244353$ på en enskild rad.

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

För det första exemplet: Låt $\text{S}$ beteckna händelsen att spelare $i$ lyckas, och låt $\text{F}$ beteckna händelsen att spelare $i$ misslyckas. De möjliga mönstren och deras sannolikheter är följande:

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

Endast $\text{SS}$ innehåller ett segment där minst $2$ spelare lyckas i följd, och dess sannolikhet är $\frac{1}{2}$. Eftersom $499122177 \times 2 \equiv 1 \pmod{998244353}$, skriv ut $499122177$.

För det andra exemplet: Även om Naniwazu-kun, som uppträder sist, inte är särskilt skicklig, går det bra så länge medhjälparna är pålitliga.

Definition av sannolikhet modulo $998244353$

Det kan bevisas att den efterfrågade sannolikheten alltid är ett rationellt tal. Under begränsningarna i detta problem garanteras att $x$ inte är delbart med $998244353$ när sannolikheten uttrycks som ett förkortat bråk $\frac{y}{x}$.

I detta fall finns det ett unikt heltal $z$ med $0 \le z \le 998244352$ sådant att $xz \equiv y \pmod{998244353}$. Skriv ut detta $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.