Universal Cup Judging System

Universal Cup

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

Naniwazu-kun affronterà la tradizionale sfida di kendama durante un programma musicale di Capodanno. Se almeno $K$ persone riescono consecutivamente, il record verrà battuto. Per massimizzare il più possibile la probabilità di successo, ha deciso di affrontare la sfida con una squadra di $N$ giocatori accuratamente selezionati.

I $N$ giocatori tenteranno il kendama in ordine dal $1$-o all'$N$-esimo. La probabilità che l'$i$-esimo giocatore ($1 \le i \le N$) riesca è $\frac{A_i}{B_i}$, e il successo o il fallimento di ciascun giocatore è indipendente.

Trova la probabilità che esista almeno un segmento in cui $K$ o più giocatori consecutivi hanno successo, modulo $998244353$.

Input

Nella prima riga sono dati gli interi $N, K$ separati da uno spazio. ($1 \le K \le N \le 2 \times 10^5$)

Nelle successive $N$ righe, l'$i$-esima riga contiene gli interi $A_i, B_i$ separati da uno spazio. ($1 \le A_i \le B_i \le 998244352$)

Output

Stampa la probabilità modulo $998244353$ su una singola riga.

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

Per il primo esempio: Sia $\text{S}$ l'evento in cui il giocatore $i$ ha successo, e $\text{F}$ l'evento in cui il giocatore $i$ fallisce. Le configurazioni possibili e le rispettive probabilità sono le seguenti:

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

Solo $\text{SS}$ contiene un segmento in cui almeno $2$ giocatori hanno successo consecutivamente, e la sua probabilità è $\frac{1}{2}$. Poiché $499122177 \times 2 \equiv 1 \pmod{998244353}$, stampa $499122177$.

Per il secondo esempio: Anche se Naniwazu-kun, che si esibisce per ultimo, non è molto abile, va tutto bene finché gli aiutanti sono affidabili.

Definizione di probabilità modulo $998244353$

Si può dimostrare che la probabilità richiesta è sempre un numero razionale. Sotto i vincoli di questo problema, quando la probabilità è espressa come frazione ridotta ai minimi termini $\frac{y}{x}$, è garantito che $x$ non è divisibile per $998244353$.

In questo caso, esiste un unico intero $z$ con $0 \le z \le 998244352$ tale che $xz \equiv y \pmod{998244353}$. Stampa questo $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.