Universal Cup Judging System

Universal Cup

حد الوقت: 2.0 s حد الذاكرة: 1024 MB مجموع النقاط: 100 قابلة للهجوم ✓
الإحصائيات

Naniwazu-kun akan mengikuti tantangan kendama tradisional dalam acara musik Malam Tahun Baru. Jika setidaknya $K$ orang berhasil secara berturut-turut, rekor akan terpecahkan. Untuk memaksimalkan peluang keberhasilan sebanyak mungkin, ia memutuskan untuk menantangnya bersama tim yang terdiri dari $N$ pemain pilihan.

Ke-$N$ pemain tersebut akan mencoba kendama secara berurutan mulai dari pemain ke-$1$ hingga ke-$N$. Peluang pemain ke-$i$ ($1 \le i \le N$) berhasil adalah $\frac{A_i}{B_i}$, dan keberhasilan atau kegagalan setiap pemain bersifat saling bebas.

Carilah peluang bahwa terdapat setidaknya satu segmen di mana $K$ atau lebih pemain berturut-turut berhasil, modulo $998244353$.

Input

Pada baris pertama, diberikan bilangan bulat $N, K$ yang dipisahkan oleh spasi. ($1 \le K \le N \le 2 \times 10^5$)

Pada $N$ baris berikutnya, baris ke-$i$ berisi bilangan bulat $A_i, B_i$ yang dipisahkan oleh spasi. ($1 \le A_i \le B_i \le 998244352$)

Output

Keluarkan peluang modulo $998244353$ dalam satu baris.

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

Untuk contoh pertama: Misalkan $\text{S}$ menyatakan kejadian bahwa pemain $i$ berhasil, dan $\text{F}$ menyatakan kejadian bahwa pemain $i$ gagal. Pola-pola yang mungkin beserta peluangnya adalah sebagai berikut:

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

Hanya $\text{SS}$ yang memuat segmen di mana setidaknya $2$ pemain berhasil secara berturut-turut, dan peluangnya adalah $\frac{1}{2}$. Karena $499122177 \times 2 \equiv 1 \pmod{998244353}$, keluarkan $499122177$.

Untuk contoh kedua: Meskipun Naniwazu-kun yang tampil terakhir tidak terlalu mahir, tidak masalah selama para pembantunya dapat diandalkan.

Definisi peluang modulo $998244353$

Dapat dibuktikan bahwa peluang yang diminta selalu merupakan bilangan rasional. Di bawah batasan masalah ini, ketika peluang dinyatakan sebagai pecahan paling sederhana $\frac{y}{x}$, dijamin bahwa $x$ tidak habis dibagi $998244353$.

Dalam hal ini, terdapat bilangan bulat unik $z$ dengan $0 \le z \le 998244352$ sedemikian sehingga $xz \equiv y \pmod{998244353}$. Keluarkan nilai $z$ ini.

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.