Universal Cup Judging System

Universal Cup

Limite de temps : 2.0 s Limite de mémoire : 1024 MB Points totaux : 100 Hackable ✓
Statistiques

Naniwazu-kun 準備喺除夕音樂節目入面參加傳統嘅劍玉挑戰。如果有至少 $K$ 個人連續成功,就會打破紀錄。為咗盡可能提高成功嘅概率,佢決定同由 $N$ 名精心挑選嘅選手組成嘅隊伍一齊挑戰。

呢 $N$ 名選手會由第 $1$ 位到第 $N$ 位按順序嘗試劍玉。第 $i$ 位選手($1 \le i \le N$)成功嘅概率係 $\frac{A_i}{B_i}$,而且每位選手嘅成功或者失敗係互相獨立嘅。

請搵出存在至少一段有 $K$ 名或以上連續選手成功嘅概率,對 $998244353$ 取模。

Input

第一行畀出兩個以空格分隔嘅整數 $N, K$。($1 \le K \le N \le 2 \times 10^5$)

接住落嚟嘅 $N$ 行,第 $i$ 行包含兩個以空格分隔嘅整數 $A_i, B_i$。($1 \le A_i \le B_i \le 998244352$)

Output

喺單一行輸出對 $998244353$ 取模之後嘅概率。

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

對於第一個範例: 設 $\text{S}$ 表示選手 $i$ 成功嘅事件,$\text{F}$ 表示選手 $i$ 失敗嘅事件。 可能嘅情況同埋佢哋嘅概率如下:

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

只有 $\text{SS}$ 包含至少 $2$ 名選手連續成功嘅區段,佢嘅概率係 $\frac{1}{2}$。 由於 $499122177 \times 2 \equiv 1 \pmod{998244353}$,所以輸出 $499122177$。

對於第二個範例: 就算最後出場嘅 Naniwazu-kun 技術唔係幾好,只要啲幫手夠穩陣就冇問題。

概率對 $998244353$ 取模嘅定義

可以證明所求嘅概率一定係有理數。喺本題嘅限制條件下,當概率表示為最簡分數 $\frac{y}{x}$ 嗰陣,保證 $x$ 唔能夠被 $998244353$ 整除。

喺呢種情況下,存在唯一嘅整數 $z$ 滿足 $0 \le z \le 998244352$ 且 $xz \equiv y \pmod{998244353}$。請輸出呢個 $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.