Universal Cup Judging System

Universal Cup

時間限制: 2.0 s 記憶體限制: 1024 MB 總分: 100 可 Hack ✓
统计

Naniwazu-kun ætlar að takast á við hina hefðbundnu kendama-áskorun í tónlistarþætti á gamlárskvöld. Ef að minnsta kosti $K$ manns tekst ætlunarverkið í röð verður metið slegið. Til að hámarka líkurnar á árangri eins mikið og mögulegt er ákvað hann að taka áskoruninni með liði af $N$ vandlega völdum leikmönnum.

Leikmennirnir $N$ munu reyna við kendama-leikfangið í röð frá þeim $1$-sta til þess $N$-ta. Líkurnar á að $i$-ti leikmaðurinn ($1 \le i \le N$) nái árangri eru $\frac{A_i}{B_i}$, og árangur eða mistök hvers leikmanns eru óháð öðrum.

Finndu líkurnar á að til sé að minnsta kosti eitt tímabil þar sem $K$ eða fleiri leikmenn í röð ná árangri, modulo $998244353$.

Input

Í fyrstu línunni eru gefnar heiltölurnar $N, K$ aðskildar með bili. ($1 \le K \le N \le 2 \times 10^5$)

Í næstu $N$ línum inniheldur $i$-ta línan heiltölurnar $A_i, B_i$ aðskildar með bili. ($1 \le A_i \le B_i \le 998244352$)

Output

Prentaðu líkurnar modulo $998244353$ í einni línu.

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

Fyrir fyrsta dæmið: Látum $\text{S}$ tákna þann atburð að leikmaður $i$ nái árangri, og $\text{F}$ tákna þann atburð að leikmaður $i$ mistakist. Möguleg mynstur og líkur þeirra eru sem hér segir:

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

Aðeins $\text{SS}$ inniheldur tímabil þar sem að minnsta kosti $2$ leikmenn ná árangri í röð, og líkur þess eru $\frac{1}{2}$. Þar sem $499122177 \times 2 \equiv 1 \pmod{998244353}$, skal prenta $499122177$.

Fyrir annað dæmið: Jafnvel þótt Naniwazu-kun, sem kemur síðastur fram, sé ekki mjög fær, þá er það í lagi svo lengi sem aðstoðarmennirnir eru áreiðanlegir.

Skilgreining á líkum modulo $998244353$

Hægt er að sanna að umbeðnar líkur eru alltaf ræð tala. Undir skorðum þessa verkefnis, þegar líkurnar eru settar fram sem fullstytt brot $\frac{y}{x}$, er tryggt að $x$ sé ekki deilanlegt með $998244353$.

Í þessu tilviki er til ótvírætt ákvörðuð heiltala $z$ með $0 \le z \le 998244352$ þannig að $xz \equiv y \pmod{998244353}$. Prentaðu þetta $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.